Find us on Google+ Kill the code: Sum of series 1 to N must be 0 where N >=3 Algorithm in Python

Monday 30 March 2015

Sum of series 1 to N must be 0 where N >=3 Algorithm in Python

Last week one of my friend told me about one of his interview question. He told me the definition of the algorithm he was asked in interview. And here is the definition.

The sum of numbers 1 to N (where N >= 3) must be zero, you can use plus (+) or minus (-) sign before any of the number. For example

for N = 3
- 1- 2+3=0
+1+2-3=0

for N = 4
-1+2+3-4=0
+1-2-3+4=0

You have to find all the possibilities for any N >=3 number.

Here is the solution to above algorithm in Python. Python is the very handy and easy language to implement such algorithms.

 import itertools 
 n = input() 
 a = [] 
 for i in range(n): 
   a.append(i+1) 
 print(a) 
 sign = list(itertools.product(['+','-'],repeat=n-1)) 
 print(sign) 
 result = [] 
 for l in sign: 
   sum1 = a[0] 
   index = 0 
   for s in l: 
     index += 1 
     if(s=='+'): 
       sum1 += a[index] 
     else: 
       sum1 -= a[index] 
   if(sum1 == 0): 
     result.append(l) 
 for l in result: 
   index = 0 
   print a[0], 
   for a1 in l: 
     index += 1 
     print a1, 
     print a[index], 
   print(" = 0") 

Please share your views in comment section.

No comments:

Post a Comment