Skip to main content
Talentd

Triples with Bitwise AND Equal To Zero - Solution & Explanation

HardArrayHash TableBit Manipulation16 min readAsked at: Philips, Flipkart
Practice this problem

Problem Statement

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

Approach Overview

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.

Approach 1: Brute Force Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^3) as there are three nested loops. Space Complexity: O(1) since no additional data structures are used.

Try this approach in the editor →

Approach 2: Using Precomputation

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Enumeration + Counting

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Triple LoopO(n^3)O(1)Useful for understanding the condition or verifying small inputs
Pair AND Precomputation with Frequency TableO(n^2 + U · n)O(U)General optimized solution when numbers have limited bit range (e.g., 16 bits)

Video Solution

982. Triples With Bitwise AND Equal To Zero (Leetcode Hard) • Programming Live with Larry • 1,202 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Triples with Bitwise AND Equal To Zero easy or hard?
Triples with Bitwise AND Equal To Zero is classified as a Hard problem because the naive solution is straightforward but inefficient. The challenge lies in recognizing that pairwise AND results can be reused, allowing the problem to be reduced from cubic time to near quadratic using bitmask precomputation.
Triples with Bitwise AND Equal To Zero Python/Java solution
Python and Java implementations follow the same pattern: compute pairwise AND results and store frequencies in a dictionary or array, then iterate through the array again to accumulate counts where the final AND equals zero. The algorithm relies on efficient bitwise operations available in both languages.
How to solve Triples with Bitwise AND Equal To Zero in O(n^2)?
Compute the AND result for every pair (i, j) and store the frequency of each result. Then for each number k, iterate through stored masks and add the frequencies where (mask & nums[k]) equals zero. The pair generation takes O(n^2), and the final counting step leverages the limited bitmask space.
What is the best approach for Triples with Bitwise AND Equal To Zero?
The most efficient approach precomputes the bitwise AND for every pair of numbers and stores their frequencies. Then each array value is combined with those results to check if the final AND equals zero. This reduces the complexity from O(n^3) to roughly O(n^2 + U · n), where U is the number of possible bit masks (up to 2^16 for this problem).
Is Triples with Bitwise AND Equal To Zero asked at Google/Amazon/Meta?
Bit manipulation and bitmask counting problems like this appear in interviews at companies such as Google, Amazon, and Meta. They test your ability to reduce higher‑order complexity using precomputation and mask properties rather than brute force enumeration.
What data structure is used in Triples with Bitwise AND Equal To Zero?
The optimized solution typically uses a hash table or a fixed-size frequency array to store counts of pairwise AND results. This structure enables fast lookups while checking whether combining a stored mask with a third number results in zero.
What is the time complexity of Triples with Bitwise AND Equal To Zero?
The brute force solution runs in O(n^3) time because it checks every triple. The optimized solution uses pairwise precomputation and runs in about O(n^2 + U · n), where U represents the possible bitmask values. With 16-bit numbers, U is at most 65,536, making the approach practical.

Ready to solve this problem?

Practice Triples with Bitwise AND Equal To Zero with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays