LIKECS03 - Editorial

Problem Link

Practice

Contest

Author: Bhuvnesh Jain

Tester: Hasan Jaddouh

Editorialist: Bhuvnesh Jain

Difficulty

EASY-MEDIUM

Prerequisites

Bitwise Operations, Greedy Algorithm

Problem

Given an array and a recursive algorithm which operates on this array, find the minimum number of elements to be inserted so that the algorithm on the resultant array never goes into infinite loop. The algorithm is as follows :

void recurse ( array a, int n )
{
	// n = size of array
	define array b currently empty
	consider all 2^n subsets of a[]
	{
		x = bitwise OR of elements in the subsets
		add x into "b" if it is not present yet
	}
	if (sizeof( b ) == 1 << k)
	{
		printf(“Won”);
		return;
	}
	recurse ( b, sizeof( b ) );
}

Quick Explanation

Try to think about powers of 2. Answer is simply the number of missing powers of 2.

Explanation

It suffices to consider only the unique elements in the initial array because a OR a = a.

Now, assume we stop the recursion the moment when we see there are no new addition of elements in the array. At this moment 2 things can happen, either the array will contain all numbers from 0 to (2^K - 1) i.e. it size will be 2^K or some of the elements might we missing from the array. Let us assume for now, we have a black box which can effectively give us the final array after we stop this recursion, i.e. generate all elements in the final array formed. If the size of array is 2^K, we do not need to insert any element and the answer is trivially 0. Otherwise, let the smallest number that is not generated be x. We will insert this number into the array and run the same black box again. This is because, since x was not generated by the previous array, for the new array to prevent infinite loop in the algorithm, x should be present. If we insert any larger number which was not generated, then again we can’t form x as OR operations always generates a number which is greater than or equal to the minimum of 2 numbers.

We will now prove that the smallest number which is not found the black box is indeed a power of 2. Let y be the number of bits set in x. Then, there are exactly 3^y ordered pairs, (u, v), whose bitwise OR is x.

One can observe that once a bit is set while doing OR operation, it will remain set in the end also. So if the algorithm given in the problem generates x, it must do so in maximum k steps of iterations. So, if it doesn’t generate x, then there should not also not generate both of (u, v) for all u, and v, such that their bitwise OR is x. Since, x >= min(u, v). So, our claim that x is the smallest number not generated will be wrong unless x is power of 2, as the only possible ordered pairs are (0, x), (x, 0) and (x, x).

Since, we proved x should be power of 2, so even after inserting x into the array, we will not generate y where y is power of 2 not initially present in array and is greater than x. Thus, we do this step again and again and greedily insert only powers of 2 into the array. In the end once all powers of 2 are present in the array, then considering only subsets of these, we can generate all numbers using OR operations. Thus, greedy strategy will be optimal here.

Hence, we simply need to find the count of powers of 2 not present in the initial array. For this, you can either mark the elements in other auxilliary space (of size 2^k) or simply insert only powers of 2 into a set and check it’s size.

Bonus Problem

Try to above black box mentioned with complexity O(2^k \log{n}).

Time Complexity

O(N \log{n}) or O(N + 2^K)

Space Complexity

O(N) or O(2^K)

Solution Links

Setter’s solution

Tester’s solution

4 Likes

@admin . I think you have posted solutions of 4th question here…

What are the subsets of an array? Plz someone give me an example…

This problem can be solved in O(N+K). Extra space required is O(K).

Check solution here

1 Like

Should’nt we check whether the array has 0 or not?0 cannot be expressed as an OR of any other two numbers as well right?

Should’nt we check whether the array has 0 or not?0 cannot be expressed as an OR of any other two numbers as well right?

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