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.

Description Solution Video 38:30

982. Triples with Bitwise AND Equal To Zero

Hard60.7% acceptance2 companies

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] < 2¹⁶

Asked at 2 companies

Philips Flipkart

Topics

38:30

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def countTriplets(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[2,1,3]

Input

[0,0,0]

Your code is saved on this device.Solution