Triples with Bitwise AND Equal To Zero - Video Solutions

Problem 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.