Блог пользователя nilsilu95

count pairs with bitwise And zeros in array
Автор nilsilu95, история, 11 лет назад, По-английски 
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
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
11 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
11 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить