LIKECS03 - Editorial

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ā€¦ :slight_smile:

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 :slight_smile:

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