Problem LinkAuthor: Bhuvnesh Jain Tester: Hasan Jaddouh Editorialist: Bhuvnesh Jain DifficultyEASYMEDIUM PrerequisitesBitwise Operations, Greedy Algorithm ProblemGiven 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 :
Quick ExplanationTry to think about powers of $2$. Answer is simply the number of missing powers of $2$. ExplanationIt 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 ProblemTry 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
This question is marked "community wiki".
asked 16 Sep '17, 01:02

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. answered 18 Sep '17, 15:13
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...
(18 Sep '17, 15:22)
2
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.
(18 Sep '17, 15:42)
1
@ceilks, thanks for pointing that out. Should have mentioned in the problem statement regarding the same.
(19 Sep '17, 22:10)

This problem can be solved in O(N+K). Extra space required is O(K). Check solution here answered 18 Sep '17, 00:28
bro you are not considering the complexity of log2() function.
(18 Sep '17, 00:41)
that expression containing log2() can be replaced by !(a[i]&(a[i]1)) i.e. if( a[i]!=0 && !(a[i]&(a[i]1)) ) {...}
(18 Sep '17, 15:04)

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? answered 18 Sep '17, 01:35
1
Sorry fr adding this as a new answer
(18 Sep '17, 01:36)
1
This sample I/o cleared it for me
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?
X needs to be 0 to give correct answer. You cant leave it uninitialised. So , empty subset added 0 to array.
(18 Sep '17, 01:39)
1
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
(18 Sep '17, 09:22)

@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? answered 19 Sep '17, 10:29
1
@o__0, it is my fault to not mention about any constraints on the elements being added.
(19 Sep '17, 22:11)

@admin . I think you have posted solutions of 4th question here.. answered 18 Sep '17, 00:22

What are the subsets of an array? Plz someone give me an example.... answered 18 Sep '17, 00:27

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? answered 18 Sep '17, 01:24

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? answered 18 Sep '17, 01:24

This problem can also be solved with this solution Time complexity : O(N.K) Extra space : O(1) The logic in both ifelse condition is same(Just thought something at that time). answered 18 Sep '17, 02:26
@sagar_kamdar Since maximum value of k is 20. The complexity can be considered as O(n) (Taking k as constant).
(18 Sep '17, 17:52)

@sachinbisht939 answered 18 Sep '17, 03:01
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.
(18 Sep '17, 15:54)
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.
(18 Sep '17, 16:59)
It didnt look that way. Tahts why I thought I should comment :)
(18 Sep '17, 17:00)
1
Understood the concern, in general it is not that way, but wrt current problem it looks like it to me.(Editted the original post)
(18 Sep '17, 17:06)
@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
(18 Sep '17, 21:59)

A solution of O(n+k) time and O(2^k) space is possible. answered 18 Sep '17, 03:39
