i can not understand the editorial. why there are exactly 3^y ordered pairs (u, v), whose or is x.
can anyone expain it? thanks
@likecs as per the @ceilks observation, whether the test cases were weak and most of the solution would fail or test cases were intended this way?
1 Like
Updated 
bro you are not considering the complexity of log2() function.
Empty subset is considered in question. So every array has 0 by default.
Sorry fr adding this as a new answer
1 Like
This sample I/o cleared it for me-
1
2 2
3 1
Answer is- Add only 2. Only possible if we consider empty subset as 0. It makes sense by this definition-
How will you calculate x?
int x=0;
//For(subset b)
x = bitwise OR of elements in the subsets
X needs to be 0 to give correct answer. You cant leave it uninitialised. So , empty subset added 0 to array.
1 Like
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