But I don’t see how 0 and the empty subset are same.For the empty subset I would say there are no elements hence do nothing at all.So I thought it essential to contain a 0, I got a WA because of this.Can you please explain why empty subset and 0 are the same?
This problem can also be solved with this solution
Time complexity : O(N.K)
Extra space : O(1)
The logic in both if-else condition is same(Just thought something at that time).
O(N.K) is worse than O(N+2^k), just saying.(For only this problem with its constraints)
For T=1, N=10^5, K=20
N.K = 2x10^6
N+2^k = 10^5 + 2^20 = 1148576, which is less than 2x10^6
Finally it is space vs time constraint…
(PS: How to reply to a comment? Could not find any button here)
A solution of O(n+k) time and O(2^k) space is possible.
Since we can go through just the powers of 2, and not the entire 2^k elements.
Edit: And I noticed it is already mentioned only that it is challenged for log2. I have it reversed and multiply by 2 won’t be a problem.
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.
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?
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
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.
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
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.
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.
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.