S_D_B's blog

No of Pair such that their Biwise AND gives power of 2.
By S_D_B, history, 4 years ago, In English

I am not sure about N, but it must be not O(n^²) solution.

  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Attempt 2 Let x&y = 2^k = (100..00)2 with k zeroes. Clearly, k+1-th bit should be 1 in both x and y (a&b=1 <=> a=b=1). And clearly x and y should have no other common bits. Let's find the number of pairs for each k. First, take only those numbers with k+1-th bit set. Consider one of them as a candidate for x. If it has ones in some other positions, then y should have zeroes in those positions. This translates into following: let mask = !(x) + 2^k and find all other numbers with k+1-st bit set, that are submasks of mask. For each k, you can find this number with dp over submasks.

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

    i couldn't get the thing "Also all other bits should be 0 in both x and y (a&b=0 <=> a=b=0)" why? if other than $$$k$$$th bit if a bit is set in atmost one of $$$x$$$ and $$$y$$$ then still their bitwise and will be power of 2.

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

      Lol, playing smart just wakig up is not a good idea! Updated.

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

        Now it's correct. I think it's time complexity will be O($$$bits$$$ * $$$bits$$$ * 2$$$bits$$$), where $$$bits$$$ = floor(log2($$$maxAi$$$)). Correct me if i am wrong?

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

          what topic should i study for understanding this? dp+ bitmask right?

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

            Sum over subset dp(called as SOS dp). Here is a nice tutorial.

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

    a AND b = 0 implies either a or b is 0 not both My proposed solution was wrong.

    → Reply