# Triples with Bitwise AND Equal To Zero
**Difficulty:** HARD
[External](https://leetcode.com/problems/triples-with-bitwise-and-equal-to-zero)
Canonical: https://scaleengineer.com/dsa/problems/triples-with-bitwise-and-equal-to-zero
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array, Hash Table
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart)
---
## Problem
Given an integer array nums, return _the number of **AND triples**_.

An **AND triple** is a triple of indices `(i, j, k)` such that:

* `0 <= i < nums.length`
* `0 <= j < nums.length`
* `0 <= k < nums.length`
* `nums[i] & nums[j] & nums[k] == 0`, where `&` represents the bitwise-AND operator.

**Example 1:**

**Input:** nums = [2,1,3]
**Output:** 12
**Explanation:** We could choose the following i, j, k triples:
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1, k=2) : 2 & 1 & 3
(i=0, j=2, k=1) : 2 & 3 & 1
(i=1, j=0, k=0) : 1 & 2 & 2
(i=1, j=0, k=1) : 1 & 2 & 1
(i=1, j=0, k=2) : 1 & 2 & 3
(i=1, j=1, k=0) : 1 & 1 & 2
(i=1, j=2, k=0) : 1 & 3 & 2
(i=2, j=0, k=1) : 3 & 2 & 1
(i=2, j=1, k=0) : 3 & 1 & 2

**Example 2:**

**Input:** nums = [0,0,0]
**Output:** 27

**Constraints:**

* `1 <= nums.length <= 1000`
* `0 <= nums[i] < 216`

# Approaches
## Brute Force Iteration
The most straightforward solution is to check every possible triple of indices (i, j, k). We can use three nested loops, each iterating from 0 to `nums.length - 1`. Inside the innermost loop, we calculate the bitwise AND of `nums[i]`, `nums[j]`, and `nums[k]`. If the result is zero, we increment a counter.
**Time:** O(N^3), where N is the length of the `nums` array. For each of the N choices for `i`, we have N choices for `j` and N choices for `k`, leading to N*N*N operations. · **Space:** O(1), as we only use a constant amount of extra space for the counter and loop variables.
**Pros:** Very simple to understand and implement.; Requires no extra space besides a few variables.
**Cons:** Extremely inefficient due to its cubic time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints (N up to 1000).
### Explanation
This approach directly translates the problem statement into code. It iterates through all combinations of three elements from the array `nums` (with replacement, as indices can be the same) and checks if their bitwise AND is zero. While simple, its performance degrades rapidly as the size of the input array increases.

```java
class Solution {
    public int countTriplets(int[] nums) {
        int n = nums.length;
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if ((nums[i] & nums[j] & nums[k]) == 0) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
*   Initialize a counter `count` to 0.
*   Use a loop for index `i` from 0 to `n-1`, where `n` is the length of `nums`.
*   Inside, use a nested loop for index `j` from 0 to `n-1`.
*   Inside, use another nested loop for index `k` from 0 to `n-1`.
*   In the innermost loop, check if the condition `(nums[i] & nums[j] & nums[k]) == 0` is true.
*   If the condition holds, increment the `count`.
*   After all loops complete, return the final `count`.

## Hashing Pairwise ANDs
We can optimize the brute-force approach by reducing one level of iteration. The condition `nums[i] & nums[j] & nums[k] == 0` can be rewritten as `(nums[i] & nums[j]) & nums[k] == 0`. This suggests we can pre-calculate the results of `nums[i] & nums[j]` for all `N*N` pairs and store their frequencies. Then, for each element `nums[k]`, we can efficiently find how many of these pre-calculated pairs satisfy the condition.
**Time:** O(N^2 + N*M), where N is `nums.length` and M is the range of values (2^16). Populating `counts` takes O(N^2). The final calculation takes O(N * M). · **Space:** O(M), where M is the maximum possible value (2^16). This is for the `counts` array.
**Pros:** Significantly more efficient than the brute-force method.; Passes the time limits for the given constraints.
**Cons:** Requires a large amount of memory for the `counts` array (O(2^16)).; The final counting step involves nested loops, one over `nums` and one over the entire value range, which can still be time-consuming.
### Explanation
First, we compute all `N*N` pairwise ANDs, `val = nums[i] & nums[j]`. We store the frequency of each resulting value `val` in an array. Since the maximum value of a number in `nums` is less than 2^16, the result of the AND operation will also be in this range. Thus, we can use an array `counts` of size 2^16 for this purpose, where `counts[v]` stores the number of pairs `(i, j)` such that `nums[i] & nums[j] == v`.

After populating the `counts` array, we iterate through each number `z` in `nums`. For each `z`, we need to find the number of pairs `(i, j)` such that `(nums[i] & nums[j]) & z == 0`. This means we must sum up `counts[v]` for all `v` where `v & z == 0`. We can do this by iterating through all possible values `v` from 0 to `2^16 - 1` and checking the condition.

```java
class Solution {
    public int countTriplets(int[] nums) {
        int maxVal = 1 << 16;
        int[] counts = new int[maxVal];
        for (int x : nums) {
            for (int y : nums) {
                counts[x & y]++;
            }
        }

        int totalTriples = 0;
        for (int z : nums) {
            for (int v = 0; v < maxVal; v++) {
                if ((z & v) == 0) {
                    totalTriples += counts[v];
                }
            }
        }
        return totalTriples;
    }
}
```
### Algorithm
*   Since the maximum value in `nums` is less than 2^16, we can use an array `counts` of size 2^16, initialized to zeros.
*   Iterate through each number `x` in `nums`.
*   Inside, iterate through each number `y` in `nums`.
*   Calculate the pairwise AND: `val = x & y`.
*   Increment `counts[val]` to store the frequency of this result.
*   Initialize a result variable `totalTriples` to 0.
*   Iterate through each number `z` in `nums`.
*   For each `z`, iterate through all possible values `v` from 0 to `2^16 - 1`.
*   If `(v & z) == 0`, it means any pair `(i, j)` whose AND result was `v` will form a valid triple with `z`. Add `counts[v]` to `totalTriples`.
*   Return `totalTriples`.

## Hashing with Sum over Subsets DP
This approach enhances the previous one by significantly optimizing the final counting step. After calculating the frequencies of pairwise ANDs (`counts[v]`), we need to compute `sum(counts[v])` for all `v` where `v & z == 0` for each `z` in `nums`. The condition `v & z == 0` is equivalent to `v` being a submask of `~z` (the bitwise complement of `z`). Instead of re-calculating this sum for each `z`, we can pre-process the `counts` array using a technique called Sum over Subsets (SOS) Dynamic Programming.
**Time:** O(N^2 + M log M), where N is `nums.length` and M is 2^16. O(N^2) for populating `dp`, O(M log M) for the SOS DP transformation, and O(N) for the final summation. This is faster than the O(N*M) term in the previous approach. · **Space:** O(M), where M is 2^16. This space is used for the `dp` array.
**Pros:** Optimal time complexity for the given constraints.; Efficiently reuses computations through dynamic programming.
**Cons:** The concept of Sum over Subsets DP is more complex and less intuitive.; Still requires O(M) space, which is a large constant.
### Explanation
The core idea is to transform the frequency array (let's call it `dp`) so that `dp[mask]` stores the sum of frequencies of all its submasks. That is, `dp[mask] = sum(counts[submask])` for all `submask` where `submask` is a submask of `mask`. This transformation can be done efficiently in O(M log M) time, where M is the value range (2^16).

Once we have this transformed `dp` array, finding the answer is straightforward. For each number `z` in `nums`, the number of pairs `(i, j)` satisfying `(nums[i] & nums[j]) & z == 0` is the sum of frequencies of all values that are submasks of `z`'s complement. This sum is exactly `dp[complement]`, where `complement` is the bitwise complement of `z`. We can sum these values for all `z` in `nums` to get the final answer.

```java
class Solution {
    public int countTriplets(int[] nums) {
        int maxVal = 1 << 16;
        int[] dp = new int[maxVal];
        
        // Step 1: Count frequencies of pairwise ANDs
        for (int x : nums) {
            for (int y : nums) {
                dp[x & y]++;
            }
        }

        // Step 2: Apply Sum over Subsets DP
        for (int i = 0; i < 16; i++) {
            for (int mask = 0; mask < maxVal; mask++) {
                if (((mask >> i) & 1) != 0) {
                    dp[mask] += dp[mask ^ (1 << i)];
                }
            }
        }

        // Step 3: Calculate the total count of triplets
        int count = 0;
        int allOnes = maxVal - 1;
        for (int z : nums) {
            // We need (val & z) == 0, which means val is a submask of ~z
            int complement = z ^ allOnes;
            count += dp[complement];
        }

        return count;
    }
}
```
### Algorithm
*   Initialize an array `dp` of size `M = 2^16` with zeros.
*   Populate `dp` with frequencies of pairwise ANDs: for each pair `(x, y)` from `nums`, increment `dp[x & y]`. This takes O(N^2).
*   Apply Sum over Subsets DP on the `dp` array to transform it. For each bit `i` from 0 to 15, and for each `mask` from 0 to `M-1`, if the `i`-th bit of `mask` is set, update `dp[mask] += dp[mask ^ (1 << i)]`.
*   After this O(M log M) transformation, `dp[mask]` will hold the sum of initial counts for all submasks of `mask`.
*   Initialize `totalTriples = 0`.
*   For each number `z` in `nums`:
    *   We need pairs `(i, j)` where `(nums[i] & nums[j])` is a submask of the complement of `z`.
    *   Calculate the complement: `complement = z ^ (M - 1)`.
    *   The number of such pairs is already computed as `dp[complement]`.
    *   Add `dp[complement]` to `totalTriples`.
*   Return `totalTriples`.

# Solutions
### Java

```java
class Solution {
public
  int countTriplets(int[] nums) {
    int mx = 0;
    for (int x : nums) {
      mx = Math.max(mx, x);
    }
    int[] cnt = new int[mx + 1];
    for (int x : nums) {
      for (int y : nums) {
        cnt[x & y]++;
      }
    }
    int ans = 0;
    for (int xy = 0; xy <= mx; ++xy) {
      for (int z : nums) {
        if ((xy & z) == 0) {
          ans += cnt[xy];
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countTriplets(vector<int> &nums) {
    int mx = *max_element(nums.begin(), nums.end());
    int cnt[mx + 1];
    memset(cnt, 0, sizeof cnt);
    for (int &x : nums) {
      for (int &y : nums) {
        cnt[x & y]++;
      }
    }
    int ans = 0;
    for (int xy = 0; xy <= mx; ++xy) {
      for (int &z : nums) {
        if ((xy & z) == 0) {
          ans += cnt[xy];
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution : def countTriplets ( self , nums : List [ int ]) -> int : cnt = Counter ( x & y for x in nums for y in nums ) return sum ( v for xy , v in cnt . items () for z in nums if xy & z == 0 )
```