You are given an array with $N$ elements. The values of the elements may be any number in the interval $[0,10^9]$. Define $f(a,b)$ as the bitwise or of all the values in the subarray $[a,b]$. Find a bound on the number of distinct values of $f(a,b)$.

Attempts: I have tried to brute force cases to find a pattern but was unsuccessful.

Please explain the reasoning behind your answer. I am a complete beginner.

  • $\begingroup$ Can you think of any bound? Do you understand the question? $\endgroup$ – Yuval Filmus Jun 13 '18 at 5:23
  • $\begingroup$ Well, I originally thought the bound would be N(N+1)/2. Apparently that wasn't a very good bound. I did get a hint to think about the number of bits that may change in a number when bitwise OR'd, but I don't know what to do with it. $\endgroup$ – Mainak Roy Jun 13 '18 at 5:31
  • $\begingroup$ This bound is actually tight for $N<30$, roughly. $\endgroup$ – Yuval Filmus Jun 13 '18 at 5:42
  • $\begingroup$ Another simple bound is $2^{30}$, which is also tight. $\endgroup$ – Yuval Filmus Jun 13 '18 at 6:44
  • $\begingroup$ Can you credit the original source of this problem? Make sure to provide proper credit any time you copy material from another source. $\endgroup$ – D.W. Jun 13 '18 at 6:59

Notice that the max value here given is 1e9. Therefore at most log(1e9) bits can be there. Suppose we fix an 'a' and iterate over 'b' such that b>=a. Thus this will form a monotonic function as bitwise OR can only increase the value of the initial operands. Moreover the OR operation can only turn a bit ON from OFF and not the other way round. So whenever the values increases that means a new bit has to be set ON. However for a fixed value of 'a' we can only turn on at most log(1e9) bits. Hence when we iterate over 'a' we can have a maximum bound of O(n)O(log(1e9)) distinct values. Hence the bound is O(nlog(MAX_VALUE))

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.