S_D_B's blog

No of Pair such that their Biwise AND gives power of 2.
By S_D_B, history, 6 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?
»
6 years ago, hide # |
← 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
  • »
    »
    6 years ago, hide # ^ |
    ← 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
  • »
    »
    6 years ago, hide # ^ |
    ← 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