I was invited to give the test and the following question was asked.
There is a weighing scale and we have an array X of integers which represents weights we are having with us. We can measure all weights which can be formed by various combinations of these weights. Suppose array is {7,9,28} then we can measure 7,9,28,2,19,16, etc. Now we are given a range [A,B], we need to tell if we can measure all weights in the range. If we can’t measure all weights in range [A,B] then we can use one extra weight which is not in the given array. Lets call it W. If there are more than one W which can be used, select the one with lowest weight.
Input : First line no of Test Cases (Less than or equal to 10)
Every test case is as follows:
First Line contains N i.e. no of given weights (N<=30)
Next line contains array X (All weights are in the range 1 to 500)
Next Line contains two space separated integers A and B (1<=A<=B<=10000 or 20000 don’t remember exactly)
Also the weight W is from range 1 to 500.
Output :
Print YES if we can measure all the weights in the range. Print the lowest W in next line.
OR
If we can’t measure all the weights in the range print NO
For some cases constraints were somewhat smaller like N<=20, range [A,B] was lesser, etc.
I thought of trying meet in the middle and generate all possible sums and differences but for N=30 I don’t know will it work.
It is like when we generated the whole dp table, if we get dp[n][w] to be false, we then check dp[n][w-1], then dp[n][w-2]… till we hit the first number to be true. say dp[n][w-k]. Then our answer would be k.
I think we need re-build the DP table for the new added weight, this requires O(W) complexity in the worst case. Now for the newly added weight once we have re-built the DP table(note- the new size of the DP table is (n+1) * W) we check if all the weight in [A, B] are set to true, if not we choose some different weight and repeat the process of rebuilding the DP table for this new weight and running a check for if all weights in the range [A, B] can be done.
More formally, select every weight in [1, 500], rebuild the DP table to (n+1) * W state and check if all weights in the range [A, B] can be done.
It would take O(W^2) in the worst case. Which is acceptable since W <= 500
