Login/RegisterInterview Puzzles :: Discussion
-
There are two gates. One goes to hell and the other goes to heaven. The gatekeeper asks a puzzle to Sahil in order to decide which gate he should open for him. Obviously if Sahil answers the puzzle correct , the gate to heaven will be opened else the gate to hell. According to the problem Sahil is given n consecutive integers from 1 to n ,which are written in a row. He has to put signs "+" and "-" in front of them so that the expression obtained is equal to 0 or, if the task is impossible to do,then Sahil should tell the gatekeeper “No solution exists for the given problem “.The gatekeeper expects Sahil to find his answer in minimum time using an efficient approach rather than examining all possible ways to place the signs. Sahil comes to you considering you as his friend. Would you help him out to get to the solution ?
Explanation :
No Best Answer on this question yet!Asked In : Sapient
Explanation :
The problem is equivalent to partitioning n integers from 1 to n into two disjoint subsets with the same sum. Disjoint subsets are the subsets with no common element. The two disjoint subsets will be :
1) a subset of numbers with a plus sign before them , and
2) a subset of numbers with a minus sign before them.
Since the sum of first n consecutive integers is S = 1 + 2 + 3 + —————— + n = (n)(n + 1)/2 ,the sum of the numbers in each of the subsets must be equal to exactly one half of S, i.e, S/2. It means that the value of S, i.e, (n)(n+1)/2 must be even for the puzzle to have a solution.
Approach :
1) It is clear that that n(n + 1)/2 is even if and only if either n is a multiple of 4 or n + 1 is a multiple of 4.
2) Indeed, if n(n + 1)/2 = 2t, this implies that n(n + 1) = 4t, and since either n or n + 1 is odd, the other must be divisible by 4. Conversely, if either n or n + 1 is a multiple of 4, and hence n(n + 1)/2 is obviously even.
3) Now considering the case when n is divisible by 4. In this case, we can, for example, partition the sequence of integers from 1 to n into n/4 groups of four consecutive integers and then put “+” sign before the first and fourth number and “-” sign before the second and third number in each of these n/4 groups. This can be understood as :
(1 – 2 – 3 + 4) + (5 – 6 – 7 + 8) + ———— + ((n – 3) – (n – 2) – (n – 1) + n) = 0. ———–(1)
4) Now considering the case when n + 1 is divisible by 4, then n = 4t – 1 , which implies n = 3 + 4(t – 1), and we can exploit the same idea by first taking care of the first three numbers as follows:
(1 + 2 – 3) + (4 – 5 – 6 + 7) + ———— + ((n – 3) – (n – 2) – (n – 1) + n) = 0. ———–(2)
So to summarize , the problem will have the following solutions :
Compute n mod 4 i.e, the remainder of the division of n by 4.
Solution 1 : If the remainder is equal to 0, insert the “+” and “-” signs as indicated by formula (1).
Solution 2 : If the remainder is equal to 3, insert the “+” and “-” signs as indicated by formula (2).
Otherwise, return the message “No solution exists for the given problem “.
Reference : Algorithmic Puzzles – Anany Levitin, Maria Levitin
