Leetcode 982. Triples with Bitwise AND Equal To Zero

Problem description:

The problem asks to find all three numbers in the array such that the result of bitwise AND operation on these three numbers equals zero.

Bitwise AND operation checks the binary representation of numbers and returns a new number where the bit is set if it is set in both numbers, otherwise, it is unset.

For example, if we have two numbers 2 (10 in binary) and 3 (11 in binary), their bitwise AND operation will result in 2 (10 in binary) because the second bit is set in both numbers.

In this problem, we basicly need to find three numbers such that the bitwise AND operation on them results in zero.

The solution should be using bitwise operation and hashing.

Approach

We are going to use a simple frequency table to calculate the times that a binary AND operation results in a certain number. For any two numbers a and b in the array, a & b results in a number and we increment the count of this number in our frequency table.

After that, we will iterate over the array again. For each number in the array and for all possible results from 0 to kMax, we will increment the answer by the count of the numbers where (num & i) equals zero.

Here is how it is done by using the previous example:`

JavaScript Solution:

1
2javascript
3class Solution {
4    countTriplets(nums) {
5        const kMax = 1 << 16;
6        let ans = 0;
7        let count = new Array(kMax).fill(0);
8
9        for (const a of nums)
10            for (const b of nums)
11                count[a & b]++;
12
13        for (const num of nums)
14            for (let i = 0; i < kMax; i++)
15                if ((num & i) == 0)
16                    ans += count[i];
17
18        return ans;
19    }
20}

In the JavaScript solution, 1 << 16 is used to calculate the power of 2. It shifts the bit of 1, 16 places to the left resulting in a number that equals 2 to the power of 16.

Python Solution:

1
2python
3class Solution:
4    def countTriplets(self, nums):
5        kMax = 1 << 16
6        ans = 0
7        count = [0]*kMax
8
9        for a in nums:
10            for b in nums:
11                count[a & b] += 1
12
13        for num in nums:
14            for i in range(kMax):
15                if (num & i) == 0:
16                    ans += count[i]
17
18        return ans

In python, array of zeros can be defined using list comprehension like [0]*kMax.

Java Solution:

1
2java
3class Solution {
4    public int countTriplets(int[] A) {
5        int MAX = 1<<16;
6        int n = A.length;
7        int[] cnt = new int[MAX];
8        for(int i=0; i<n; i++){
9            for(int j=0; j<n; j++){
10                cnt[A[i]&A[j]]++;
11            }
12        }
13        
14        int res = 0;
15        for(int i=0; i<n; i++){
16            for(int j=0; j<MAX; j++){
17                if((A[i] & j) == 0){
18                    res +=cnt[j];
19                }
20            }
21        }
22        
23        return res;
24    }
25}

In Java, arrays are not dynamic. We need to set the size at the time of creation and cannot change it later.

C# Solution:

1
2csharp
3public class Solution {
4    public int CountTriplets(int[] A) {
5        int MAX = 1<<16;
6        int n = A.Length;
7        int[] cnt = new int[MAX];
8        for(int i=0; i<n; i++){
9            for(int j=0; j<n; j++){
10                cnt[A[i]&A[j]]++;
11            }
12        }
13        
14        int res = 0;
15        for(int i=0; i<n; i++){
16            for(int j=0; j<MAX; j++){
17                if((A[i] & j) == 0){
18                    res +=cnt[j];
19                }
20            }
21        }
22        
23        return res;
24    }
25}

The C# solution is the same as Java.

C++ Solution:

1
2cpp
3class Solution {
4public:
5    int countTriplets(vector<int>& A) {
6        int kMax = 1<<16;
7        int ans = 0;
8        vector<int> count(kMax, 0);
9
10        for (const int a : A)
11            for (const int b : A)
12                count[a & b]++;
13
14        for (const int num : A)
15            for (int i = 0; i < kMax; i++)
16                if ((num & i) == 0)
17                    ans += count[i];
18
19        return ans;
20    }
21};

In C++, vector is used instead of an array, which is similar but more flexible than array because it can change its size dynamically.In all the solutions, note that the number of elements in the count array or ArrayList is 2 to the power of 16, which is the largest 16-bit number, to accommodate every possible result of the AND operation.

Consequently, the time complexity of this problem is O(n²). This is because we iterate over the list of nums twice, checking the bitwise AND of each pair of numbers. The third loop, although it iterates over the 2 to the power of 16, does not contribute remarkably to the time complexity because it is not nested within another loop.

These solutions may not be optimal since each nested loop could potentially result in a performance hit. However, they provide a good starting point. Further optimizations could include using a more efficient data structure to store the frequency of AND results, or reducing the number of iterations over the list of nums.

In conclusion, with the right combination of data structures, bitwise operations, and iteration strategy, the problem of finding triplets in an array that perform the AND operation resulting in zero becomes manageable.