2
$\begingroup$

Let's say we have given set of integers $A = \{x_1, x_2, x_3, x_4, \dots, x_n\}$, consisting of exactly $n$ values, all of them positive integers. Now the problem is to find the maximum value of bitwise or operation of all possible pairs $(x_i, x_j)$

We define bitwise or as bitwise operation that returns true if atleast one of the bits is turned on, in most programming languages it is declared as "|".

Edit: We assume that the numbers in the set can be written with at most 17 bits, or they are smaller than $2^{17}$.

For example, we have: $n=4, A = \{12, 3, 4, 11\}$ the maximum value of bitwise or will be $15$, because $12|3=15, 11|4=15, 12|11=15$ so the result is $15$ and we have exactly $3$ pairs that give this result.

My thinking

Obviously we can take each pair and see what is their bitwise or, but this leads us to solution in $O(N^2)$, and I think that there is much faster solution, I think that we don't need to calculate the bitwise or of all numbers, and we can only calculate it for some numbers.

$\endgroup$
  • $\begingroup$ Do you have any limit on the size of the numbers? For example, perhaps there are $O(\log n)$ bits long? $\endgroup$ – Yuval Filmus Oct 20 '17 at 13:22
  • $\begingroup$ We can assume that the numbers will be less than $2^{17}$ $\endgroup$ – someone12321 Oct 20 '17 at 14:09
  • $\begingroup$ This can help you: geeksforgeeks.org/… $\endgroup$ – Andrey França Oct 20 '17 at 14:11
  • 1
    $\begingroup$ What's the context where you encountered this problem? Can you cite the source? What else did you try, beyond noting that $O(N^2)$ is too slow? Where did you get stuck? We're happy to help you understand the concepts but just solving exercise-style problems/practice problems for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Oct 20 '17 at 14:41
  • $\begingroup$ If the number of bits is fixed then this can be solved in $O(n)$. First determine how many of the possible words appears 0, 1, or at least 2 times. Given this information, look up the answer in a table. This shows that to make this problem interesting theoretically, you need to include the number of bits as a parameter. $\endgroup$ – Yuval Filmus Oct 20 '17 at 15:32
1
$\begingroup$

If the numbers have width $c\log n$ then there is a randomized $O(n^{2-1/O(\log c)})$ algorithm that finds the maximum OR correctly with high probability. The idea is to find the maximum OR bit by bit, MSB to LSB. We can do this using $c\log n$ queries of the following form: "Is there an OR whose $k$ most significant bits are $b_1\ldots b_k$?". Each such query is equivalent (up to bitwise operations) to the query (applied to a different list): "Is there an OR in which all bits are 1?". Abboud, Williams, and Yu gave a randomized $O(n^{2-1/O(\log c)})$ time algorithm for this problem (which they call Boolean orthogonal detection, flipping 0s and 1s).

If the numbers have unbounded width then (depending on the exact model of computation), there is no $O(n^{2-\epsilon})$ time algorithm (assuming SETH). Indeed, deciding whether the maximum OR is all 1s is the same as Boolean orthogonal detection, for which the aforementioned hardness is known (see for example these lecture notes of Russel Impagliazzo).

Finally, if the numbers have bounded width then there is a simple $O(n)$ algorithm. The algorithm computes the set of numbers appearing in the input, and looks up the answer at a (rather large) table.

$\endgroup$
  • $\begingroup$ I edited the post, the numbers will be less than $2^{17}$ $\endgroup$ – someone12321 Oct 21 '17 at 5:41
  • $\begingroup$ In that case, there is an $O(1)$ algorithm. See the last paragraph. $\endgroup$ – Yuval Filmus Oct 21 '17 at 5:43
  • $\begingroup$ How do you create the lookup table, what do you keep in it? $\endgroup$ – someone12321 Oct 21 '17 at 5:57
  • $\begingroup$ Sorry, I meant $O(n)$ algorithm. I create the lookup table in advance. I keep in it the answer for every set of inputs. This isn't a practical algorithm, though, since the lookup table is quite large. $\endgroup$ – Yuval Filmus Oct 21 '17 at 5:58

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.