How to calculate number of unordered pairs in an array whose bitwise AND is a power of 2
. For ex if the array is [10,7,2,8,3]
. The answer is 6
.
Explanation(0-based index):
a[0]&a[1] = 2
a[0]&a[2] = 2
a[0]&a[3] = 8
a[0]&a[4] = 2
a[1]&a[2] = 2
a[2]&a[4] = 2
The only approach that comes to my mind is brute force. How to optimize it to perform in O(n) or O(n*log(n))?
The constraints on the size of array can be at max 10^5
. And the value in that array can be upto 10^12
.
Here is the brute force code that I tried.
int ans = 0;
for (int i = 0; i < a.length; i++) {
for (int j = i + 1; j < a.length; j++) {
long and = a[i] & a[j];
if ((and & (and - 1)) == 0 && and != 0)
ans++;
}
}
System.out.println(ans);
If you are just looking for the number of un-ordered pair and the array is sorted in ascending order. You can use this formula n * (n - 1) / 2. Suppose your array has n elements, for example 3 in your case. It will be 3 * 2 / 2 = 3.
Initialize a variable, say totalAND, to store Bitwise AND of each element from these pairs. Iterate over the array and generate all possible pairs (arr[i], arr[j]) from the given array. For each pair (arr[i], arr[j]), update the value of totalAND = (totalAND & arr[i] & arr[j]). Finally, print the value of totalAND.
Count unordered pairs (i,j) such that product of a[i] and a[j] is power of two. Count of pairs whose bitwise AND is a power of 2. Number of pairs whose sum is a power of 2. Count of elements which cannot form any pair whose sum is power of 2. Highest power of 2 less than or equal to given number.
The key to solve this problem is that A xor B = K => A xor K = B. xor(^): The xor operation or the exclusive-or operation gives 0 as output when the inputs are same and 1 as output when the inputs are different. The idea is that if a and b are different, then output is 1 or else, it is 0.
Although this answer is for a smaller range constraint (possibly suited up to about 2^20), I thought I'd add it since it may add some useful information.
We can adapt the bit-subset dynamic programming idea to have a solution with O(2^N * N^2 + n * N)
complexity, where N
is the number of bits in the range, and n
is the number of elements in the list. (So if the integers were restricted to [1, 1048576] or 2^20, with n
at 100,000, we would have on the order of 2^20 * 20^2 + 100000*20 = 421,430,400 iterations.)
The idea is that we want to count instances for which we have overlapping bit subsets, with the twist of adding a fixed set bit. Given Ai
-- for simplicity, take 6 = b110
-- if we were to find all partners that AND to zero, we'd take Ai
's negation,
110 -> ~110 -> 001
Now we can build a dynamic program that takes a diminishing mask, starting with the full number and diminishing the mask towards the left
001
^^^
001
^^
001
^
Each set bit on the negation of Ai
represents a zero, which can be ANDed with either 1 or 0 to the same effect. Each unset bit on the negation of Ai
represents a set bit in Ai
, which we'd like to pair only with zeros, except for a single set bit.
We construct this set bit by examining each possibility separately. So where to count pairs that would AND with Ai
to zero, we'd do something like
001 ->
001
000
we now want to enumerate
011 ->
011
010
101 ->
101
100
fixing a single bit each time.
We can achieve this by adding a dimension to the inner iteration. When the mask does have a set bit at the end, we "fix" the relevant bit by counting only the result for the previous DP cell that would have the bit set, and not the usual union of subsets that could either have that bit set or not.
Here is some JavaScript code to demonstrate with testing at the end comparing to the brute-force solution.
var debug = 0;
function bruteForce(a){
let answer = 0;
for (let i = 0; i < a.length; i++) {
for (let j = i + 1; j < a.length; j++) {
let and = a[i] & a[j];
if ((and & (and - 1)) == 0 && and != 0){
answer++;
if (debug)
console.log(a[i], a[j], a[i].toString(2), a[j].toString(2))
}
}
}
return answer;
}
function f(A, N){
const n = A.length;
const hash = {};
const dp = new Array(1 << N);
for (let i=0; i<1<<N; i++){
dp[i] = new Array(N + 1);
for (let j=0; j<N+1; j++)
dp[i][j] = new Array(N + 1).fill(0);
}
for (let i=0; i<n; i++){
if (hash.hasOwnProperty(A[i]))
hash[A[i]] = hash[A[i]] + 1;
else
hash[A[i]] = 1;
}
for (let mask=0; mask<1<<N; mask++){
// j is an index where we fix a 1
for (let j=0; j<=N; j++){
if (mask & 1){
if (j == 0)
dp[mask][j][0] = hash[mask] || 0;
else
dp[mask][j][0] = (hash[mask] || 0) + (hash[mask ^ 1] || 0);
} else {
dp[mask][j][0] = hash[mask] || 0;
}
for (let i=1; i<=N; i++){
if (mask & (1 << i)){
if (j == i)
dp[mask][j][i] = dp[mask][j][i-1];
else
dp[mask][j][i] = dp[mask][j][i-1] + dp[mask ^ (1 << i)][j][i - 1];
} else {
dp[mask][j][i] = dp[mask][j][i-1];
}
}
}
}
let answer = 0;
for (let i=0; i<n; i++){
for (let j=0; j<N; j++)
if (A[i] & (1 << j))
answer += dp[((1 << N) - 1) ^ A[i] | (1 << j)][j][N];
}
for (let i=0; i<N + 1; i++)
if (hash[1 << i])
answer = answer - hash[1 << i];
return answer / 2;
}
var As = [
[5, 4, 1, 6], // 4
[10, 7, 2, 8, 3], // 6
[2, 3, 4, 5, 6, 7, 8, 9, 10],
[1, 6, 7, 8, 9]
];
for (let A of As){
console.log(JSON.stringify(A));
console.log(`DP, brute force: ${ f(A, 4) }, ${ bruteForce(A) }`);
console.log('');
}
var numTests = 1000;
for (let i=0; i<numTests; i++){
const N = 6;
const A = [];
const n = 10;
for (let j=0; j<n; j++){
const num = Math.floor(Math.random() * (1 << N));
A.push(num);
}
const fA = f(A, N);
const brute = bruteForce(A);
if (fA != brute){
console.log('Mismatch:');
console.log(A);
console.log(fA, brute);
console.log('');
}
}
console.log("Done testing.");
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With