Triples with Bitwise AND Equal To Zero solution and explanation
6 more videos on this problem
982. Triples With Bitwise AND Equal To Zero (Leetcode Hard)Programming Live with Larry · 38:30 · 1K views
982. Triples With Bitwise AND Equal To Zero (Leetcode Hard) Part 2Programming Live with Larry · 8:15 · 972 views
Leetcode 982. Triples with Bitwise AND Equal To Zero (2 sum)LetsCode · 6:47 · 155 views
No Sound Leetcode 982: Triples with Bitwise AND Equal To ZeroExtremeProgrammer · 1:28 · 43 views
LeetCode 982: Triples with Bitwise AND Equal To ZeroAlitaCode · 27:20 · 41 views
LeetCode Problem #982 Triples with Bitwise And Equal to Zero神戸万事屋 · 0:41 · 1 view
LeetCode Problem #982 Triples with Bitwise and Equal To Zero神戸万事屋 · 0:32
The problem
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.length0 <= j < nums.length0 <= k < nums.lengthnums[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 <= 10000 <= 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).
def countTriplets(nums):
count = 0
for i in range(len(nums)):
for j in range(len(nums)):
for k in range(len(nums)):
if (nums[i] & nums[j] & nums[k]) == 0:
count += 1
return count
nums = [2, 1, 3]
print("Output:", countTriplets(nums))import java.util.*;
public class Main {
public static int countTriplets(int[] nums) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length; j++) {
for (int k = 0; k < nums.length; k++) {
if ((nums[i] & nums[j] & nums[k]) == 0) {
count++;
}
}
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {2, 1, 3};
System.out.println("Output: " + countTriplets(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
int countTriplets(vector<int>& nums) {
int count = 0;
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < nums.size(); j++) {
for (int k = 0; k < nums.size(); k++) {
if ((nums[i] & nums[j] & nums[k]) == 0) {
count++;
}
}
}
}
return count;
}
int main() {
vector<int> nums = {2, 1, 3};
cout << "Output: " << countTriplets(nums) << endl;
return 0;
}function countTriplets(nums) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < nums.length; j++) {
for (let k = 0; k < nums.length; k++) {
if ((nums[i] & nums[j] & nums[k]) === 0) {
count++;
}
}
}
}
return count;
}
let nums = [2, 1, 3];
console.log("Output:", countTriplets(nums));#include <stdio.h>
int countTriplets(int* nums, int numsSize) {
int count = 0;
for (int i = 0; i < numsSize; i++) {
for (int j = 0; j < numsSize; j++) {
for (int k = 0; k < numsSize; k++) {
if ((nums[i] & nums[j] & nums[k]) == 0) {
count++;
}
}
}
}
return count;
}
int main() {
int nums[] = {2, 1, 3};
int size = sizeof(nums) / sizeof(nums[0]);
printf("Output: %d\n", countTriplets(nums, size));
return 0;
}using System;
class Program {
public static int CountTriplets(int[] nums) {
int count = 0;
for (int i = 0; i < nums.Length; i++) {
for (int j = 0; j < nums.Length; j++) {
for (int k = 0; k < nums.Length; k++) {
if ((nums[i] & nums[j] & nums[k]) == 0) {
count++;
}
}
}
}
return count;
}
static void Main() {
int[] nums = {2, 1, 3};
Console.WriteLine("Output: " + CountTriplets(nums));
}
}Python implementation uses three nested loops to consider all possible triples, counting those where the AND operation is equal to zero.
Time Complexity: O(n^3). Space Complexity: O(1).
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.
def countTriplets(nums):
from collections import defaultdict
freq = defaultdict(int)
for i in nums:
for j in nums:
freq[i & j] += 1
count = 0
for k in nums:
for key in freq.keys():
if (k & key) == 0:
count += freq[key]
return count
nums = [2, 1, 3]
print("Output:", countTriplets(nums))import java.util.*;
public class Main {
public static int countTriplets(int[] nums) {
int[] freq = new int[65536];
for (int x : nums) {
for (int y : nums) {
freq[x & y]++;
}
}
int count = 0;
for (int x : nums) {
for (int i = 0; i < 65536; i++) {
if ((x & i) == 0) {
count += freq[i];
}
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {2, 1, 3};
System.out.println("Output: " + countTriplets(nums));
}
}#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int countTriplets(vector<int>& nums) {
vector<int> freq(65536, 0);
for (auto& x : nums) {
for (auto& y : nums) {
++freq[x & y];
}
}
int count = 0;
for (auto& x : nums) {
for (int i = 0; i < 65536; ++i) {
if ((x & i) == 0) {
count += freq[i];
}
}
}
return count;
}
int main() {
vector<int> nums = {2, 1, 3};
cout << "Output: " << countTriplets(nums) << endl;
return 0;
}function countTriplets(nums) {
let freq = Array(65536).fill(0);
nums.forEach(x => {
nums.forEach(y => {
freq[x & y]++;
});
});
let count = 0;
nums.forEach(z => {
for (let i = 0; i < freq.length; i++) {
if ((z & i) === 0) {
count += freq[i];
}
}
});
return count;
}
let nums = [2, 1, 3];
console.log("Output:", countTriplets(nums));#include <stdio.h>
#include <string.h>
#define MAX 65536
int countTriplets(int* nums, int numsSize) {
int freq[MAX] = {0};
for (int i = 0; i < numsSize; i++) {
for (int j = 0; j < numsSize; j++) {
freq[nums[i] & nums[j]]++;
}
}
int count = 0;
for (int k = 0; k < numsSize; k++) {
for (int i = 0; i < MAX; i++) {
if ((nums[k] & i) == 0) {
count += freq[i];
}
}
}
return count;
}
int main() {
int nums[] = {2, 1, 3};
int size = sizeof(nums) / sizeof(nums[0]);
printf("Output: %d\n", countTriplets(nums, size));
return 0;
}using System;
class Program {
static int CountTriplets(int[] nums) {
int[] freq = new int[65536];
foreach (int x in nums) {
foreach (int y in nums) {
freq[x & y]++;
}
}
int count = 0;
foreach (int z in nums) {
for (int i = 0; i < freq.Length; i++) {
if ((z & i) == 0) {
count += freq[i];
}
}
}
return count;
}
static void Main() {
int[] nums = {2, 1, 3};
Console.WriteLine("Output: " + CountTriplets(nums));
}
}In Python, the dictionary is employed to handle frequency of pairs' AND results. This method minimizes direct loop interactions and utilizes earlier pair computations to boost lookup for valid triples.
Time Complexity: O(n^2 + n * MAX), MAX is the range of bit-combination (65536). Space Complexity: O(MAX) for the frequency dictionary.
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.
function countTriplets(nums: number[]): number {
const mx = Math.max(...nums);
const cnt: number[] = Array(mx + 1).fill(0);
for (const x of nums) {
for (const y of nums) {
cnt[x & y]++;
}
}
let ans = 0;
for (let xy = 0; xy <= mx; ++xy) {
for (const z of nums) {
if ((xy & z) === 0) {
ans += cnt[xy];
}
}
}
return ans;
}func countTriplets(nums []int) (ans int) {
mx := slices.Max(nums)
cnt := make([]int, mx+1)
for _, x := range nums {
for _, y := range nums {
cnt[x&y]++
}
}
for xy := 0; xy <= mx; xy++ {
for _, z := range nums {
if xy&z == 0 {
ans += cnt[xy]
}
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3). Space Complexity: O(1). |
| Using Precomputation | Time Complexity: O(n^2 + n * MAX), MAX is the range of bit-combination (65536). Space Complexity: O(MAX) for the frequency dictionary. |
| Enumeration + Counting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Triple Loop | O(n^3) | O(1) | Useful for understanding the condition or verifying small inputs |
| Pair AND Precomputation with Frequency Table | O(n^2 + U · n) | O(U) | General optimized solution when numbers have limited bit range (e.g., 16 bits) |
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.