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
1 Like
that expression containing log2() can be replaced by !(a[i]&(a[i]-1))
i.e. if( a[i]!=0 && !(a[i]&(a[i]-1)) ) {ā¦}
your input is not allowed by the constraints. Tha elements of a are supposed to < 2^k, in your case 2^2=4. so 4,6,7 canāt be in the initial array.
2 Likes
Really interesting observationā¦
I didnāt think About thatā¦ 
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ā¦
Tell me if Iām wrongā¦
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.
2 Likes
It depends on your input size. If I put N=1000, K= 100, then I think you will see which is better.
2^k grows very fast with input size, so you need to be careful.
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.
O(N.K) is worse than O(N+2^k)
It didnt look that way. Tahts why I thought I should comment
Understood the concern, in general it is not that way, but wrt current problem it looks like it to me.(Editted the original post)
1 Like
@sagar_kamdar Since maximum value of k is 20. The complexity can be considered as O(n) (Taking k as constant).
@sachinbisht939 good thought, but going in numbers I calculated above, it is good to have N+2^k or N+K instead of N.K
(How to comment on the post by someone else, not getting any button there to reply)
If the kth bit of x is 0, the kth bits of u and v have to be 0 too. If the kth bit of x is 1 you have 3 possibilities for the kth bits of u and v: 01, 10 and 11. So 3 (mutually independent) possibilities for each of the y set bits: 3^y in total.
1 Like
@ceilks, thanks for pointing that out. Should have mentioned in the problem statement regarding the same.
1 Like
@o__0, it is my fault to not mention about any constraints on the elements being added.
1 Like