Triples with Bitwise AND Equal To Zero: Precompute Pairwise Results
LeetCode Triples with Bitwise AND Equal To Zero (Problem 982) asks you to count all triples (i, j, k) where nums[i] & nums[j] & nums[k] == 0. The indices i, j, and k range from 0 to n - 1, and they do not need to be distinct. At first glance, this looks like it requires checking every possible triple, but there is a much faster way.
The problem
You are given an array of non-negative integers nums. Count the number of triples (i, j, k) such that the bitwise AND of nums[i], nums[j], and nums[k] equals zero. The same index can appear multiple times in a triple, so (0, 0, 0) is valid as long as nums[0] & nums[0] & nums[0] == 0.
For example, given nums = [2, 1, 3], the binary representations are 2 = 10, 1 = 01, and 3 = 11. One valid triple is (0, 1, 1) because 2 & 1 & 1 = 0.
The brute force approach
The most direct solution uses three nested loops. For each combination of (i, j, k), compute nums[i] & nums[j] & nums[k] and check if the result is zero. With n elements, that gives n^3 combinations to check. For n = 1000, that is a billion operations, which is far too slow.
You might try to prune some branches early by computing nums[i] & nums[j] in the middle loop and skipping the inner loop when the pairwise result already has bits set that no element in the array can clear. But worst case, that does not help enough.
The key insight
You can split the three-way AND into two phases. First, precompute all pairwise AND values nums[i] & nums[j] and count how often each result appears. Then, for each pairwise result, check which elements in nums produce zero when AND-ed with it. This reduces the work from O(n^3) to O(n^2) for the precomputation plus O(n * max_val) for the lookup phase.
The pairwise AND of two numbers produces a value that is at most max(nums). Many different pairs can produce the same pairwise result, and you only need to know the count, not the specific pairs. By grouping identical pairwise results together, you avoid redundant work in the third loop.
Step-by-step walkthrough
Let's trace through the algorithm on nums = [2, 1, 3]. We first build a frequency map of all pairwise AND results, then scan through nums one more time to find which pairwise results AND to zero with each element.
Step 1: Understand the brute force O(n^3) approach
Check all triples (i, j, k). For nums = [2, 1, 3] with n=3, that is 27 combinations. For large n, this is too slow.
Step 2: Precompute all pairwise ANDs with frequency counts
Loop over all pairs (a, b) and store the count of each a AND b result in a hash map. This takes O(n^2) time.
Step 3: For each pairwise result, find third values that produce 0
For each entry (ab_val, freq) in the map, loop over nums. If ab_val AND c equals 0, add freq to the answer.
Step 4: Sum up all valid triples
Each pairwise AND that produces 0 with some c contributes its frequency count. The total is the number of valid triples.
The code
def countTriplets(self, nums):
from collections import Counter
pair_and = Counter()
for a in nums:
for b in nums:
pair_and[a & b] += 1
count = 0
for ab, freq in pair_and.items():
for c in nums:
if ab & c == 0:
count += freq
return count
The first double loop builds a Counter that maps each pairwise AND result to the number of pairs that produce it. The second phase iterates over every entry in the counter and every element in nums. When a pairwise result AND-ed with c equals zero, you add the frequency of that pairwise result to the total count. This works because each unit of frequency represents a distinct (i, j) pair, and combining it with the current c gives a valid triple.
The number of distinct keys in pair_and is at most 2^16 = 65536 because the problem constrains values to 0 through 2^16 - 1. This means the second phase does at most 65536 * n work, which is fast enough for the given constraints.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Brute force (3 nested loops) | O(n^3) | O(1) |
| Precompute pairwise ANDs | O(n^2 + n * max_val) | O(max_val) |
The first phase runs in O(n^2) to compute all pairwise ANDs. The second phase runs in O(D * n) where D is the number of distinct pairwise AND values, bounded by max_val. Since max_val can be up to 2^16, the second phase is at most O(65536 * n). For n = 1000, the total is about 1,000,000 + 65,536,000, which is well within time limits.
The building blocks
Precomputation to reduce loop depth
The core technique is splitting a three-way operation into two phases: precompute partial results, then combine with the remaining variable. This is the same idea behind matrix chain multiplication and many "meet in the middle" strategies. Whenever you have a three-way combination and the intermediate result has a bounded range, precomputation can collapse one loop entirely.
Frequency counting with hash maps
Instead of storing every individual pair, you aggregate pairs by their result. A Counter (or dictionary) maps each distinct AND value to how many pairs produced it. This lets you treat all pairs with the same result as a single group, multiplying the count by however many third elements produce zero. This pattern of "group by result, multiply by frequency" appears throughout combinatorics and optimization problems.
Edge cases
All elements are zero. When every element is 0, every triple satisfies 0 & 0 & 0 == 0. The answer is n^3. The algorithm handles this naturally because pair_and[0] = n^2, and every c satisfies 0 & c == 0.
Single element array. When n = 1, there is exactly one triple: (0, 0, 0). The answer depends on whether nums[0] & nums[0] & nums[0] == 0, which is true only if nums[0] == 0.
All elements are the same non-zero value. If every element equals some value v where v & v != 0, then v & v & v = v, which is non-zero. The answer is 0. The algorithm correctly finds that pair_and[v] = n^2 and no c satisfies v & c == 0.
Array contains both 0 and non-zero values. Any triple that includes 0 as any operand will AND to 0 if the other two AND to 0 as well. But a triple like (i, j, k) where nums[k] = 0 always works because anything & 0 = 0. The algorithm counts these correctly through the frequency map.
Maximum value elements. When elements use all 16 bits (value 65535), the pairwise AND can produce any value from 0 to 65535. The second phase checks all distinct pairwise results against all elements, which is the worst case for the number of counter entries but still within the time bound.
Powers of two. When elements are distinct powers of two, pairwise ANDs produce 0 for any two different elements and the original value for same-element pairs. This creates many zero entries in the frequency map, leading to a large count of valid triples.
From understanding to recall
The key idea in this problem is the split between precomputation and lookup. Once you internalize "precompute pairwise results, then scan for the third operand," you can apply the same structure to any problem with three-way combinations. The specific detail to remember is that AND has a bounded output range, which makes the frequency map small enough to iterate over efficiently.
When practicing, focus on two things: (1) recognizing when a three-nested-loop problem can be split into two phases, and (2) remembering that bitwise AND can only produce values up to max(nums), which bounds the number of distinct intermediate results. These two observations together give you the full solution.
Spaced repetition helps you recall the split strategy quickly. The first time you solve this, the precomputation idea might take a while to surface. After a few repetitions, you will see "three-way AND" and immediately think "precompute pairwise, scan for third." That pattern becomes automatic.
Related posts
- Single Number - Uses XOR cancellation to find a lone unpaired element. A different bitwise operation, but the same mindset of exploiting bitwise properties to avoid brute-force enumeration.
- Bitwise AND of Numbers Range - AND across a contiguous range preserves only the common binary prefix. A complementary perspective on how AND behaves across multiple values.
- Hamming Distance - Counts differing bit positions between two numbers. Builds fluency with binary representations and per-bit analysis that supports problems like this one.