Greg and Chris

Hard
0/120
profile
Contributed by
2 upvotes
Asked in company
Facebook

Problem statement

Greg has an array ‘ARR’ of size ‘N’. One day Greg got into a fight with Chris and in the heat of the moment, Chris deleted Greg’s array. Fortunately, Greg had the subset-sums array ‘subsetSum’ of the original array ‘ARR’ which contains the sum of every subset of the original array. Help Greg to recover the original Array.

An array ‘subset’ is the subset of an array ‘ARR’ if ‘subset’ can be obtained from ‘ARR’ by deleting some(or possibly zero or all) elements of the array ‘ARR’.

Note: There can be more than one answers. You can print any of that.

For Example : 
‘N’ = 4, ‘subsetSum’ = {-1, 0, 3, 4, 4, 5, 8, 9}.

Now in this example, the original array was {-1, 4, 5}. As when we calculate the subset sum of this array we will get the given array. The subset of the this array and its sum is:
{} -> sum is 0.
{-1} -> sum is -1.
{4} -> sum is 4.
{5} -> sum is 5.
{-1, 4} -> sum is 3.
{-1, 5} -> sum is 4.
{4, 5} -> sum is 9.
{-1, 4, 5} -> sum is 8.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input format contains ‘T’, denoting the number of test cases. Then each test case follows.

The first line of each test case contains an integer ‘N’, denoting the number of elements in the original array ‘ARR’. 

The second line of the test case contains an array of ‘2 ^ N’ integers denoting the subset-sum array ‘subsetSum’.
Output Format : 
For each test case, print an array denoting the original array ‘ARR’.

Output for every query will be printed in a separate line.
Note : 
You are not required to print anything explicitly. It has already been taken care of. Just implement the functions.

If the path is valid then it will print true else it will print false.
Constraints : 
1 <= T <= 10
2 <= ‘N’ <= 15
-5000 <= ‘subsetSum[i]’ <= 5000

Time Limit: 1 second
Sample Input 1 :
2
2
0 0 0 0
3
0 1 2 3 6 5 4 3
Sample Output 1 :
True
True
Explanation For Sample Output 1 :
For the first example, the elements {0, 0} is the only possible solution, as the subset sum array of {0, 0} is {0, 0, 0, 0}.

For the second example, the subset sum of the array {1, 2, 3} is:
{} sum is 0.
{1} sum is 1.
{2} sum is 2.
{3} sum is 3.
{1, 2} sum is 3.
{1, 3} sum is 4. 
{2, 3} sum is 5.
{1, 2, 3} sum is 6.
Hence the answer is {1, 2, 3}.
Sample Input 2 :
2
1
0 1
3
-3 -2 -1 0 0 1 2 3
Sample Output 2 :
True
True
Explanation For Sample Output 2 :
For the first example, the original array is {1} as the subset sum array of {1} is {0, 1}.

For the second example, there can be two possible array for this subset sum {1, 2, -3}:
{} sum is 0.
{1} sum is 1.
{2} sum is 2.
{-3} sum is -3.
{1, 2} sum is 3.
{1, -3} sum is -2. 
{2, -3} sum is -1.
{1, 2, -3} sum is 0.

and {-1, -2, 3}:
{} sum is 0.
{-1} sum is -1.
{-2} sum is -2.
{3} sum is 3.
{-1, -2} sum is -3.
{-1, 3} sum is 2. 
{-2, 3} sum is 1.
{-1, -2, 3} sum is 0.
Hence the answer can be {1, 2, -3} or {-1, -2, 3}.
Hint

First, try to find a single number and then find the subset-sum of the remaining numbers and repeat this process

Approaches (1)
Brute Force

Let’s take the subset-sum array be {s1, s2, s3… s(2^n)} in ascending order and the original array be {n(k), n(k-1)… n1, z1, z2… z(t), p1, p2… p(q)} in ascending order, where n1 to n(k) are ‘k’ negative integers, z1 to z(t) are ‘t’ zeros and p1 to p(q) are ‘q’ positive integers in the array. Now take a look at the first two numbers of the ‘subsetSum’ array ‘s1’ and ‘s2’. It is obvious that ‘s1’ is the sum of all the negative numbers ‘n1’ to ‘nk’ and ‘s2’ can be either the sum of ‘n2’ to ‘nk’ or ‘p1’ + the sum of ‘n1’ to ‘nk’. Hence on subtracting ‘s2’ with ‘s1’ we will get some value f1. Now, f1 can either be ‘p1’ or ‘n1’. Now we have to check that for every element in the ‘subsetSum’ array there exist a number which on subtracting either ‘p1’ or ’n1’ gives another number that is present in the array if any of the ‘p1’ or ’n1’ does not give a value which is present in the array we will discard it. we will repeat this process till we find all the integers. 

 

The steps are as follows:

  1. Take a vector ‘answer’ to store the final answer.
  2. Take a vector ‘cpy’ and copy the whole array ‘subsetSum’ into the array ‘cpy’.
  3. Sort the given ‘cpy’ array in ascending order.
  4. While the size of  the vector ‘cpy’ is greater than one:
    • Take two vectors ‘l’ and ‘r’ in which we will store the subset-sum values, ‘l’ denotes the values not having the current integer while ‘r’ will store the values having the current integer. The array containing zero will be the valid subset-sum array.
    • Take an integer ‘num’ equal to cpy[1] - cpy[0].
    • Iterate through the whole array ‘cpy’ from 0 to cpy.size()(say iterator be i):
      • Check if the current element is not INT_MIN:
        • Push the current element ‘cpy[i]’ into ‘l’ and 'cpy[i]’ + ‘num’ into ‘r’.
        • Iterate through the array ‘cpy’ again to update the value of ‘cpy[i]’ + ‘num’ to INT_MIN.
    • Check if either of ‘l’ contains ‘zero’ or not:
      • Push ‘num’ to ‘answer’.
      • Update ‘cpy’ = ‘l’.
    • Else:
      • Push negative of ’num’ to ‘answer’.
      • Update ‘cpy’ = ‘r’.
Time Complexity

O(N * 2 ^ N). Where N is the total number of integers in the original array.

 

As we are finding each integer one by one, and for each integer, we are iterating through the whole ‘subsetSum’ array.

Hence, the time complexity is O(N * 2 ^ N).

Space Complexity

O( N ).

 

Since we are taking a vector of size N to store the original array. 

Hence the space complexity is O( N ).

Code Solution
(100% EXP penalty)
Greg and Chris
Full screen
Console