LIKECS03 - Editorial

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?

1 Like

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).

@sachinbisht939

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.

Solution

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

1 Like

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.

6 Likes

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

@likecs and @ceilks are anagrams ???

4 Likes

Updated :slight_smile:

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… :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.