Code

The solution of problem 982 is showed below. You can also find it here.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int countTriplets(vector<int>& A) {
int n = A.size();
int inv[1 << 16] = { 0 };
for( auto a : A ) {
for( int i = 0; i < ( 1 << 16 ); ++i )
if( ( a & i ) == 0 )
++inv[i];
}
int ret = 0;
for( int i = 0; i < n; ++i ) {
for( int j = 0; j < n; ++j ) {
ret += inv[A[i] & A[j]];
}
}
return ret;
}
};

Solution

The core method to solve it is to treat one number previously and traverse all combination of two numbers $a \& b$ in the vector. In this way, we can reduce the time complexity from $O(N^3)$ to $O(N^2)$. The treatment is to pre-calculate each number $a$ in the vector to find with which number $b$ $a \& b$ would get $0$.

Valuable Method

The pre-treating method is really important when solving problems. If we enumerate all three numbers combination, for example $a \& b \& c$, we would repeatly calculate & operator with $c$ for many times. By remembering it, we could use more space to reduce run time. Moreoever, we could also store the result of $a \& b$ and check the result by $c$.