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.length0 <= j < nums.length0 <= k < nums.lengthnums[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 <= 10000 <= nums[i] < 216Problem Overview: Given an integer array nums, count the number of triples (i, j, k) such that nums[i] & nums[j] & nums[k] == 0. The challenge is that a naive three‑loop solution quickly becomes too slow for larger arrays.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
Iterate through every possible triple using three nested loops. For each combination (i, j, k), compute nums[i] & nums[j] & nums[k] and increment the count if the result equals zero. This approach uses direct bit manipulation with the AND operator. While simple to implement and useful for verifying correctness on small inputs, it performs n^3 checks and becomes impractical when n grows.
Approach 2: Pair AND Precomputation with Hashing (O(n^2 + U · n) time, O(U) space)
Reduce the problem by first computing the bitwise AND of every pair (i, j). Store the frequency of each result in a map or array where the key is nums[i] & nums[j]. This step takes O(n^2). Then iterate through every value k in the array and check which precomputed pair results produce zero when ANDed with nums[k]. For every stored mask where (mask & nums[k]) == 0, add its frequency to the answer. Because numbers are limited to 16 bits in the original constraints, the universe of masks U is at most 2^16, making this scan feasible.
This technique relies on fast bitwise operations and efficient counting using a hash table or frequency array. Instead of evaluating triples directly, you break the problem into pairs plus a third element. The reduction from cubic to roughly quadratic time is the key optimization.
Recommended for interviews: Start by explaining the brute force O(n^3) idea to show understanding of the condition. Then move to the pair‑AND precomputation approach. Interviewers typically expect this optimization because it demonstrates comfort with array iteration patterns, frequency counting, and reasoning about bit masks.
This approach involves iterating through all possible triples of indices (i, j, k) and checking if the bitwise AND of nums[i], nums[j], and nums[k] is zero. This requires three nested loops thereby leading to a time complexity of O(n^3).
The implementation uses three nested loops to iterate through each index combination (i, j, k) of the array and checks if the bitwise AND of elements at these indices is zero.
Time Complexity: O(n^3) as there are three nested loops. Space Complexity: O(1) since no additional data structures are used.
In this approach, we first precompute the AND results of all pairs in the array and store their frequencies. This reduces redundant calculations by leveraging symmetry and associative properties of the AND operation, and the solution can be evaluated in fewer nested loops. The precomputed states make it feasible to efficiently evaluate potential zero AND triples.
This solution precomputes all pairwise AND results and uses them to evaluate potential triples more efficiently by combining earlier results with a single loop.
Time Complexity: O(n^2 + n * MAX) where MAX is the number of different possible AND results. Space Complexity: O(MAX) for the frequency storage.
First, we enumerate any two numbers x and y, and use a hash table or array cnt to count the occurrences of their bitwise AND result x \& y.
Then, we enumerate the bitwise AND result xy, and enumerate z. If xy \& z = 0, then we add the value of cnt[xy] to the answer.
Finally, we return the answer.
The time complexity is O(n^2 + n times M), and the space complexity is O(M), where n is the length of the array nums; and M is the maximum value in the array nums, with M leq 2^{16} in this problem.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3) as there are three nested loops. Space Complexity: O(1) since no additional data structures are used. |
| Using Precomputation | Time Complexity: O(n^2 + n * MAX) where MAX is the number of different possible AND results. Space Complexity: O(MAX) for the frequency storage. |
| Enumeration + Counting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Triple Loop | O(n^3) | O(1) | Useful for understanding the condition or verifying small inputs |
| Pair AND Precomputation with Frequency Table | O(n^2 + U · n) | O(U) | General optimized solution when numbers have limited bit range (e.g., 16 bits) |
982. Triples With Bitwise AND Equal To Zero (Leetcode Hard) • Programming Live with Larry • 1,188 views views
Watch 6 more video solutions →Practice Triples with Bitwise AND Equal To Zero with our built-in code editor and test cases.
Practice on FleetCode