LeetCode 982 - Triples with Bitwise AND Equal To Zero

This problem asks us to count the number of triples (i, j, k) from an integer array nums such that the bitwise AND of the three numbers at these indices equals zero. In other words, we want all combinations where nums[i] & nums[j] & nums[k] == 0.

leetcodehardarrayhash-tablebit-manipulation

LeetCode Problem 982

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Bit Manipulation

Solution

Problem Understanding

This problem asks us to count the number of triples (i, j, k) from an integer array nums such that the bitwise AND of the three numbers at these indices equals zero. In other words, we want all combinations where nums[i] & nums[j] & nums[k] == 0.

The input is an array of integers where each element ranges from 0 to 2^16 - 1 (i.e., 0 to 65535), and the length of the array is up to 1000. The output is a single integer representing the number of valid triples.

Edge cases to consider include arrays that contain only zeros, arrays with maximum values, or arrays with repeated elements. A naive implementation may struggle due to the potential number of combinations - for n = 1000, a straightforward triple-nested loop would result in a billion iterations, which is not feasible.

Approaches

The brute-force approach iterates over all possible triples (i, j, k) using three nested loops. For each triple, it computes the bitwise AND and checks if it equals zero. While this approach is simple and correct, it has a cubic time complexity of O(n^3), which is too slow for n = 1000.

The optimal approach relies on the observation that bitwise AND is associative and commutative. We can precompute all possible pairs (i, j) and store the frequency of their AND results in a hash map. For each number nums[k], we can then iterate over the keys of this map and check if key & nums[k] == 0. If so, we add the count from the map to the result. This reduces the time complexity significantly because we avoid iterating through all triples directly.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(1) Triple nested loop over all elements
Optimal O(n^2 * 2^16) in worst case O(2^16) Precompute pairwise ANDs and use a hash map for counts

Algorithm Walkthrough

  1. Initialize a hash map to store the frequency of AND results of all pairs (nums[i] & nums[j]).
  2. Iterate through every pair (i, j) in the array and compute nums[i] & nums[j]. Increment the frequency of this value in the hash map.
  3. Initialize a variable result to zero to store the count of valid triples.
  4. Iterate through each number nums[k] in the array. For each key in the hash map, check if key & nums[k] == 0. If true, add the corresponding frequency from the map to result.
  5. Return result.

Why it works: Precomputing the pairwise ANDs and counting their frequencies ensures that for each potential third element, we efficiently sum all pairs that will produce zero when ANDed with it. This avoids the cubic iteration over all triples.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def countTriplets(self, nums: List[int]) -> int:
        pair_count = defaultdict(int)
        
        # Count all pairwise AND results
        for i in nums:
            for j in nums:
                pair_count[i & j] += 1
        
        result = 0
        
        # For each number, sum all pair counts that AND to 0 with it
        for num in nums:
            for key, count in pair_count.items():
                if key & num == 0:
                    result += count
        
        return result

Explanation: We first build a dictionary pair_count to store how many times each AND result occurs among all pairs. Then, for each number in the array, we iterate over all keys in the dictionary and check if ANDing with this number gives zero. The sum of all such counts is our final result.

Go Solution

func countTriplets(nums []int) int {
    pairCount := make(map[int]int)
    
    for _, i := range nums {
        for _, j := range nums {
            pairCount[i & j]++
        }
    }
    
    result := 0
    for _, num := range nums {
        for key, count := range pairCount {
            if key & num == 0 {
                result += count
            }
        }
    }
    
    return result
}

Explanation: The Go implementation mirrors the Python solution. We use a map pairCount to track pairwise AND frequencies. Unlike Python, Go requires explicit initialization of maps. Iteration and addition are handled in the same way.

Worked Examples

Example 1: nums = [2,1,3]

  1. Compute pairwise ANDs:
  • 2&2=2, 2&1=0, 2&3=2, 1&2=0, 1&1=1, 1&3=1, 3&2=2, 3&1=1, 3&3=3
  • pair_count = {2:3, 0:2, 1:3, 3:1}
  1. For each num:
  • num=2 → keys that AND with 2 give 0 → key=0 → add 2 to result
  • num=1 → keys that AND with 1 give 0 → key=0 → add 2 to result
  • num=3 → keys that AND with 3 give 0 → key=0 → add 2 to result
  1. Continue for all keys → final result = 12

Example 2: nums = [0,0,0]

  1. All pairwise ANDs = 0 → pair_count = {0:9}
  2. Each number AND 0 = 0 → add 9 each time for 3 numbers → result = 27

Complexity Analysis

Measure Complexity Explanation
Time O(n^2 + n*uniquePairs) Precomputing pairs is O(n^2). Iterating over map keys for each num is O(n*uniquePairs). In worst case, uniquePairs <= 2^16
Space O(2^16) Storing pairwise AND counts in a hash map with keys up to 2^16

The main saving is that the pairwise map avoids iterating through all n^3 triples directly. In practice, the number of unique AND values is much smaller than the theoretical maximum.

Test Cases

# Provided examples
assert Solution().countTriplets([2,1,3]) == 12  # mixture of small numbers
assert Solution().countTriplets([0,0,0]) == 27  # all zeros

# Edge cases
assert Solution().countTriplets([1]) == 1  # single element
assert Solution().countTriplets([65535,65535]) == 0  # max values, no zero AND
assert Solution().countTriplets([0,1,2,3]) == 36  # small diverse set
assert Solution().countTriplets([5,1,0]) == 12  # zero guarantees many triples
Test Why
[2,1,3] Small diverse set to check correct counting
[0,0,0] Edge case where all numbers are zero
[1] Minimum input size
[65535,65535] Maximum values to test no valid triples
[0,1,2,3] Mix of zero and small numbers
[5,1,0] Zero allows multiple valid triples

Edge Cases

Single-element array: A single-element array still forms a triple with repetition (i,j,k) all equal to 0, if the number is 0. The implementation correctly handles repeated indices.

Array with all zeros: Every combination of indices produces zero, leading to n^3 triples. Our algorithm handles this efficiently using the precomputed pair map.

Array with maximum numbers: Elements equal to 2^16 - 1 will rarely produce zero when ANDed. The algorithm correctly excludes these pairs by checking key & num == 0 during the final accumulation.

These edge cases ensure the algorithm correctly handles small inputs, repeated zeros, and maximum boundary values without errors or overcounting.