Last Updated: 17 Oct, 2021
Greg and Chris
Hard
Asked in company
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.
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
Approaches
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:
- Take a vector ‘answer’ to store the final answer.
- Take a vector ‘cpy’ and copy the whole array ‘subsetSum’ into the array ‘cpy’.
- Sort the given ‘cpy’ array in ascending order.
- 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 the current element is not 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’.