1
\$\begingroup\$

What I am trying to do is to find count of alternating numbers such that it alternates with -ve and positive sign for e.g.: 1 -2 3 -4 would get me 4 3 2 1 as from 1 to -4 including the two numbers there are 4 numbers. Similarly, for 1 1 -3 2 would get me 1 3 2 1. Now I have the code but I cannot optimise it and it returns me a time limit exceeded error even though it works for moderate input stream.

Here, alternating means like first number is positive and second number is negative and next number is positive and so on. So if input is 1 -2 3 -4 then from number 1 maximum I can travel to -4 such that there is an alternating sequence. So the count =3 numbers + the number itself i.e 4. Again from -2 if I travel from I can go till -4 as it alternates from negative positive and negative. So it is 2 numbers +1=3 again. Similarly, for r=each position I get it as 4 3 2 1. Now suppose number is 1 1 -3 2 then there is no number for 1 to find the next alternating number immediately so 1.

So for 1 1 -3 2 for 1 since there is no immediate -ve number it is a 1.For the second 1 I can traverse to a -3 and 2 i.e 2 number so count=2+1=3.For -3 all I find is a single 2 so count is 1+1=2.For the last number it is 1.So the answer is 1 3 2 1

Sample input: 1 -2 1 -3 2

Output: 4 3 2 1

j=0
count=0
length=(raw_input())
st=map(int,raw_input().split())
while j+1 < len(st):
     k=j+1
     count=0
     temp=j
     while k<len(st) and ((st[k]<0 and st[j]>0) or (st[k]>0 and st[j]<0)):
       count+=1
       k+=1
       j+=1
     print count+1,
     j=temp+1
print 1
\$\endgroup\$
  • \$\begingroup\$ ok here alternating means like first number is positive and second number is negative and next number is positive and so on.So if input is 1 -2 3 -4 then from number 1 maximum I can travel to -4 such that there is a alternating sequence.So the count =3 numbers + the number itself i.e 4.Again from -2 if I travel from I can go till -4 as it alternates from negative positive and negative.So it is 2 numbers +1=3 again.Simmilarly for r=each position I get it as 4 3 2 1.Now suppose number is 1 1 -3 2 then there is no number for 1 to find the next alternating number immediatedly so 1. \$\endgroup\$ – Leo B Jacob Oct 9 '17 at 10:48
  • \$\begingroup\$ So for 1 1 -3 2 for 1 since there is no immediate -ve number it is a 1.For the second 1 I can traverse to a -3 and 2 i.e 2 number so count=2+1=3.For -3 all I find is a single 2 so count is 1+1=2.For the last number it is 1.So the answer is 1 3 2 1. \$\endgroup\$ – Leo B Jacob Oct 9 '17 at 10:55
  • \$\begingroup\$ done .......... \$\endgroup\$ – Leo B Jacob Oct 9 '17 at 10:56
1
\$\begingroup\$

This problem is much easier looking it backwards: Instead of processing the input in the order given, process it in reverse order. You know the last number in your answer will be 1, because no numbers follow it. Now the previous one could be a 2 if the sign is different with the last one or a 1 if its the same sign.

So basically, each step back can either add 1 to the list of consecutive numbers with alternating signs or reset the count to 1.

The code:

    length=(raw_input())
    st = map(int,reversed(raw_input().split()))

    answ = []
    count = 0
    for i, num in enumerate(st):
         count += 1
         if i > 0 and (num < 0) == (st[i - 1] < 0):
            count = 1
        answ.append(str(count)) 

    print " ".join(reversed(answ))  
\$\endgroup\$
0
\$\begingroup\$

Are you sure you should print intermediate results of just final answer? If the final is enought then there is no reason to return back to initial j after inner loop and complexity of algorithm become O(n):

j = 0
max = 0
length = (raw_input())
st = map(int,raw_input().split())
while j+1 < len(st):
   k = j + 1
   count = 1
   while k<len(st) and ((st[k]<0 and st[k-1]>0) or (st[k]>0 and st[k-1]<0)):
     count += 1 
     k += 1
     j += 1
   for c in range(1, count+1)[::-1] :
     print c
   j += 1
\$\endgroup\$
  • \$\begingroup\$ I did not understand when you said intermediate answer. \$\endgroup\$ – Leo B Jacob Oct 9 '17 at 11:07
  • \$\begingroup\$ My output for 1 -2 3 -1 should be 4 3 2 1.Your answer seems wrong to me @zefick \$\endgroup\$ – Leo B Jacob Oct 9 '17 at 11:17
  • \$\begingroup\$ OK, I understood your task and edited the code. \$\endgroup\$ – Zefick Oct 9 '17 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.