DLN's blog

How to solve this problem on bitmasks
By DLN, history, 4 years ago, In English

Problem Statement — Given an array count the no. of distinct pairs of elements such that their AND(&) is an exact power of 2.

array size <= 1e5 and 1 <= a[i] <= 2^12

Example — array -> [10 7 8 2 3] ; answer = 6

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

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

if bitwise and of x and y is a power of 2 then abs(x-y) must be a power of 2. so build a set of the given array first. then for each element p in the set, search the number of occurences of element p+pow(2,i) in the set for each i satisfying 0<=i<=12 and p&pow(2,i)=0.

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

First keep the count of each number present in the array.
Simply brute force every pair (x,y) such that 1<=x<=y<=2^12 and check the bitwise AND of each pair.
If it is a power of 2, then do the following:
Case 1: if(x!=y)
then add count(x)*count(y) to the answer
Case 2: if(x==y)
then add (count(x)*(count(x)-1))/2 to the answer

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

    Thanks, this solution is pretty simple

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

    Time complexity??

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

      Its O(2^24) which is nearly 10^7 operations which is fine.

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

        what if the question has (1 <= a[i] <= 2^20) as constraints for each element, then what approach do we use to avoid TLE.

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

can you please provide the question link? (i wanted to check if my solution works or not).

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

    The question is from HackerRank certification test.

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

I think we can use a trie and search for the required no. of pairs. Iterate over all the elements of the array. For a given no. in array there will be 12 possibilities of placing a 1 (not exactly 12, depends upon the position of 1s in the the selected numbers) , and traverse the trie and sum the total no. of such numbers which will make every bits 0 except one bit. I hope it will pass the time constraint!! If you want to study trie then follow this link: https://www.hackerearth.com/practice/data-structures/advanced-data-structures/trie-keyword-tree/tutorial/ Read whole advanced data structures, that will be quite beneficial for you!!

→ Reply