You are not logged in. Please login at www.codechef.com to post your questions!

×

# LIKECS03 - Editorial

Practice

Contest

Author: Bhuvnesh Jain

Editorialist: Bhuvnesh Jain

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

Setter's solution

Tester's solution

This question is marked "community wiki".

asked 16 Sep '17, 01:02 6★likecs
3.7k2481
accept rate: 9%

 6 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 7★ceilks 1.8k●9 accept rate: 36% 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) 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) ceilks7★ 1 @ceilks, thanks for pointing that out. Should have mentioned in the problem statement regarding the same. (19 Sep '17, 22:10) likecs6★
 4 @likecs and @ceilks are anagrams ??? answered 28 Sep '17, 10:59 81●4 accept rate: 0%
 1 This problem can be solved in O(N+K). Extra space required is O(K). Check solution here answered 18 Sep '17, 00:28 10●2 accept rate: 0% 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)
 1 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 4★adiabhi 42●3 accept rate: 0% 1 Sorry fr adding this as a new answer (18 Sep '17, 01:36) adiabhi4★ 1 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. (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) adiabhi4★
 1 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 answered 18 Sep '17, 10:00 4★siva2697 21●3 accept rate: 0% 2 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. (18 Sep '17, 15:04) ceilks7★
 1 @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 3★o__0 133●5 accept rate: 0% 1 @o__0, it is my fault to not mention about any constraints on the elements being added. (19 Sep '17, 22:11) likecs6★
 0 @admin . I think you have posted solutions of 4th question here.. answered 18 Sep '17, 00:22 2●1 accept rate: 0% Updated :) (18 Sep '17, 00:25) likecs6★
 0 What are the subsets of an array? Plz someone give me an example.... answered 18 Sep '17, 00:27 1●1 accept rate: 0%
 0 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 4★adiabhi 42●3 accept rate: 0%
 0 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 4★adiabhi 42●3 accept rate: 0% Empty subset is considered in question. So every array has 0 by default. (18 Sep '17, 01:26)
 0 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). answered 18 Sep '17, 02:26 11●3 accept rate: 0% @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)
 0 @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) answered 18 Sep '17, 03:01 1●1 accept rate: 0% 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. And below I have given n+k, which is better than n+2^k. (18 Sep '17, 16:59) O(N.K) is worse than O(N+2^k) 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 (How to comment on the post by someone else, not getting any button there to reply) (18 Sep '17, 21:59)
 0 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. answered 18 Sep '17, 03:39 1●1 accept rate: 0%
 0 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 answered 18 Sep '17, 23:15 2★sinhtu 1 accept rate: 0% 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. (19 Sep '17, 00:05) ceilks7★
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,722
×1,024
×593
×184
×99
×7

question asked: 16 Sep '17, 01:02

question was seen: 2,720 times

last updated: 28 Sep '17, 10:59