nilsilu95's blog

count pairs with bitwise And zeros in array
By nilsilu95, history, 9 years ago, In English 
This was question i faced during hp thinkathon (contest has ended).What should be the approach to reduce time complexity less than bruteforce(O(n*n))

You have been given an integer array A on size N. You must report the number of ordered pairs (i,j) such that A[i] & A[j] is zero.
Here '&' denotes the BITWISE AND.
(i,j) and (j,i) are considered different.

Input
First line contains T-Number of Test cases. First line of each test contains N. Next line contains N integers - the ith integer A[i].
Output
Output the number of such pairs for each test case.

Constraints 
T ≤ 10
N ≤ 100000
A[i] ≤ 1000000

Sample Input()
1
5
41 47 34 40 29 
Sample Output()
 2
Explanation
These are the required pairs 3 5 5 3
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Ok, I have an idea and I think it should work, it's as the following:

1 - Let cnt[i] be the count of numbers that 2^i is used inside it's decimal representation, this is can be done by O(N*log(MAX_NUM)).

Example: 6 = 2^2 + 2^1 so now cnt[2]+=1, cnt[1] += 1 (the index is the power) and save the powers for the number (6) for step 2.

2 - You can now loop on all the items, and let the current item be a so loop on all the powers that are used in the representation of a from the previous step then the answer for the current item will be:

N - (Sum For All Cnt[Powers(a)]), So such this algorithm should work in : O(N * log(N)).

Hope it helps.

EDIT: Please provide us with the problem link.

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

    This is not going to work
    Take the following test case
    3
    3 6 0
    for this the cnt Array will be like
    cnt[0] = 1, cnt[1] = 2, cnt[2] = 1
    Now for 3, the answer is 3-cnt[0]-cnt[1] that is 0
    But (3&0) == 0, so the above algorithm fails

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

      Thanks for pointing to this

      But is there any way to handle such this problem? I thought about bitmask but I can't handle it efficiently.

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

lets create a binary trie supporting these operations:

define a pattern for a number x as its binary representation flipping the 1's into 0's and the 0's into '?', for x = 29, pattern = 0?000?, the first digit is the less significant one (reversed binary string), a '?' means it can be anything in that position.

1.- insert(x) insert x as binary string
2.- query(pattern) count how many times the pattern appears in the trie

let ans = 0
for each value x in your array
 build a pattern p from x
 ans += trie.query(p)*2
 trie.insert(x)

each query is multiplied by 2 for counting the unordered pairs.

Im not sure about the complexity using the easy way for coding this but there are many possible optimizations to speed it up.

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

    The solution works fine but its complexity is exponential

    For any number n, if its binary representation contains the k 0's then time complexity of above code is O(2k log2n)

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

      2^k = 10^6 which is acceptable, you can optimize it storing how many leafs are in each subtree, when your value has no more '? to check, returns that value.

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

        Time complexity is, where k is number of bits of A_i,

        build a pattern p from x -> k

        count how many times the pattern appears in the trie -> 2^k (can be optimized to N maybe?) , since you should check every branches in worst case.

        It leads time complexity O(N^2) if optimized, nothing different with brute-force solution.

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

divide into two groups > whole number and number with last bits 1,

work it recursively as obtaining complementary event.

I will add C++ implementation shortly.

UPD 1: I implemented it with first bit, not last bit. http://ideone.com/UzPzMh

UPD 2: Time complexity is O(M log M) where, M is constraint of A[i], in this problem 1 000 000.

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

    An iterative version: http://ideone.com/er93s5

    EDIT: As people are asking for more explanations, dp[i] counts the number of integers in input that have all of the bits in i set, for example, dp[5] is all integers of the form xxxxx1x1.

    Then it's just inclusion-exclusion: we count the number of pairs of integers, minus the number of pairs with 1 bit in common, plus the pairs of integers with 2 bits in common, minus the pairs of integers with 3 bits in common...

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

    Can you explain this in little more detail ? Thank you

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

      number of pairs which has '&' operation of two values have 0 at first bit = number of all pairs — number of pairs which has '&' operation of two values have 1 at first bit

      '&' operation of two values have 1 at first bit means, all values have 1 at first bit.

      Therefore, we separated numbers which have 1 at first bit and calculated it with other bit recursively with above equation.

      → Reply