0
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Can you think of any bound? Do you understand the question? $\endgroup$ Commented Jun 13, 2018 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
    Commented Jun 13, 2018 at 5:31
  • $\begingroup$ This bound is actually tight for $N<30$, roughly. $\endgroup$ Commented Jun 13, 2018 at 5:42
  • $\begingroup$ Another simple bound is $2^{30}$, which is also tight. $\endgroup$ Commented Jun 13, 2018 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.
    Commented Jun 13, 2018 at 6:59

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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