input :
1
4 2
0 4 6 7
output:?
if we follow above approach we get result as 2 since 2 and 1 are missing but if we consider all subsets of intial array we need not add any elements hence answer would be 0. pls clarify this
While the initial eleemnts of the array can’t be \geq2^k, there is no such restriction on additional elements.
Consider the case n=2, k=2, a=\{0,3\}. The algorithm presented here would find that 2 elements are missing (since 1 and 2 are not in the initial array). But if you take 4 as additonal element, i.e. a'=\{0,3,4\} the resulting array after one step is b=\{0,3,4,7\} which has 2^k elements. So the algorithm terminates with just one additional element.
Yes, I overlooked that test case.But this could have been clarified in the question,(x=0 for empty subset).But with the given test case, it is perhaps understandable this was not done.Thank you
But in most of the arrays, i believe, adding an element >= 2^k would add too many elements in a single recusrion which would result in sizeof(b) > (1<<k), thus making our task impossible…
Yes, by adding higher (>=k) powers of two you are doubling the size of the resulting array, so adding just higher powers only works if the original array already generates an array with a size of a power of two.
I was talking with respect to the constraints given, I took the max limits for N and K. I agree 2^k will grow faster, but K is only till 20 in this problem.
And below I have given n+k, which is better than n+2^k.