elements's blog

The smallest subset with maximum bitwise OR.
By elements, history, 4 years ago, In English

Can someone help me with this problem.

Given an array A of N numbers. We are required to find the size of the smallest subset of the array such that Bitwise OR is maximum possible.

$$$1 \leq N \leq 10^5$$$

$$$1 \leq A[i] \leq 10^6$$$

Sample input:
5
1 2 3 4 5


Sample output:
2
  • Vote: I like it
  • +20
  • Vote: I do not like it

Comments Comments (28)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by elements (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Post the link to the original problem.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I couldn't find any. This was one of the questions asked for Round 1 of HackwithInfy conducted by Infosys.

    → Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

This has been asked before here.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh sorry. I didn't find it. Thank you.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      This problem has A[i]<=10^6. So, I think its possible to solve it in A[i]log(A[i])^2. We can create polynomial where exponent is equal to value and coefficient is equal to one if that value is present in the array and otherwise 0. Then, we perform or convolutions repeatedly until the element corresponding to maximum or has non-zero coefficient. It will take obviously <= log(A[i]) steps atmax and each step costs A[i]log(A[i]).
      Edit: Using binary lifting kind of thing you can achieve complexity O(A[i]log(A[i])log(log(A[i]))). Not sure if that would be much faster.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        Whatever you said is quite above my level. I think I should leave this problem.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +23 Vote: I do not like it

          Suppose input is: $$$A[] = {1,2,8,7}$$$

          max or is 15

          Consider Polynomial: $$$P$$$ = 0 $$$x^0$$$ + 1 $$$x^1$$$ + 1 $$$x^2$$$ + 0 $$$x^3$$$ ... 1 $$$x^7$$$ + 1 $$$x^8$$$ + 0 (Coefficient of $$$x^i$$$ is count of i in $$$A$$$)

          Define Multiplication Operation on Polynomials:

          $$$A[0..n] , B[0..n]$$$ and $$$C = A * B$$$

          where $$$C[z]$$$ = $$$\sum_{z = x|y} A[x] B[y]$$$

          (Coefficient of $$$x^i$$$ is count of $$$j,k$$$ such that $$$A[j]|B[k] = i$$$)

          Now back to Question, If $$$P$$$ is the polynomial defined above coefficient of $$$x^i$$$ in $$$P*P$$$ is the number of $$$j,k$$$ such that $$$A[j]|A[k] = i$$$ (you will get all possible ORs after taking two elements from P)

          similarly in $$$P*P*P$$$ coefficient of $$$x^i$$$ is number of $$$j,k,l$$$ such that $$$A[j]|A[k]|A[l] = i$$$

          you need to repeatedly multiply $$$P$$$ until coefficient of $$$P^{n}[max Or]$$$ is non zero then report index of {n}

          Ok, all this is fine but can we do this multiplication fast? Yes, we can!

          to learn more about this algorithm open this

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Can you share the code for this problem? I am still confused about the solution approach. I tried it for a long time but was not able to solve it.

            → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It's really useful, thanks for sharing

            → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        You can actually optimize that to O(A[i]log(A[i])). Using the transform for OR convolution you have something like a[i] = number of ways to get exact mask of i, transformed to A[i] = number of ways to get submasks of i, since the or of submasks of i are also submasks of i. You can convolute it using exponentiation then you can extract the a[maximum size of mask using or possible] in O(A[i]) using inclusion-exclusion, so you get O(A[i]log(A[i])) for the initial transformation and O(A[i]) for finding if that certain mask was possible to get * O(log(A[i])) being the maximum size of the set.

        → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If you want to master binary search or segment tree then this is one of the best questions. Binary search on answer can be used.

What is the maximum OR?
 It is the OR of all the elements. Let it be MaxOR.
Maintain a segment tree to find bitwise OR for any given range.

Now do binary search with l=1 and r=N.
In each step, find if there exists any subarray that has OR=MaxOR by traversing through the array and using the segtree to compute OR of range (i,i+mid), where mid is the value of binary step.
→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    He's asking about subset and not subarray. Then why do we need segment tree? Sorry if i am missing something.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      My bad. Extremely sorry, misread the question, unable to delete.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        It's okay. Don't be sorry. Your answer was helpful for me even though you answered a different question. Thanks.

        → Reply
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

This problem was also asked in Google Internship Online Coding Round.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I found this, but it is too simple to be correct. Can anyone verify?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It is incorrect. Take [12, 10, 5] for example, that algorithm will output 3 while the answer is 2.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thanks

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Please explain approach for solving this question. I not get any logic.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This isn't a obvious question. Look at this comment. You will have some idea.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Are you sure?. I got same question with same constraint in Google test

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yeah. You don't have to assume it is right, just because it was asked by Google. Moreover, technically it is not wrong, as you should be able to squeeze the algorithm mentioned above in the time limit if you optimize it a bit.

            → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If I remove the numbers whose mask is a subset of an already existing number. Would this be a correct solution.

For Example if we have A=[1,3,4,2] then here 1 is a submask of 3 so I remove it 2 is a submask of 4 Hence my final subset will be [4,3]

I would like to know if this solution is correct. Can anybody please help me here?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry for necroposting, but I had a similar idea; my idea is that as usual I find the maximum OR by finding the OR of all the elements of the array.

    And then I take the element with the maximum number of set bits and then at every iteration I remove those submasks from all the numbers in the array and keep on doing this till I hit the required maximum OR.

    So I wanted to ask if this approach is correct; can someone please confirm? If it is incorrect, please tell me a testcase where this approach would fail.

    Thanks in advance!

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had the same idea too. Could you please let me know if you were able to find if this is a right approach or not?

    → Reply