Triples with Bitwise AND Equal To Zero — Problem & Solution
Triples with Bitwise AND Equal To Zero solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Triples with Bitwise AND Equal To Zero is a hard coding problem on arrays, hash table and bit manipulation, asked in Amazon and Flipkart interviews.
- Difficulty: Hard
- Topics: Arrays, Hash Table, Bit Manipulation
- Asked at: Amazon, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums, count the AND triples: ordered triples of indices (i, j, k) with 0 <= i, j, k < nums.length (indices may repeat) such that nums[i] AND nums[j] AND nums[k] == 0.
Return the number of AND triples.
Example 1
Input: nums = [1,2]
Output: 6
Explanation: Of the 8 index triples only `(0,0,0)` (AND 1) and `(1,1,1)` (AND 2) are non-zero.
Example 2
Input: nums = [0]
Output: 1
Example 3
Input: nums = [4,4,3]
Output: 18
Explanation: The AND is non-zero only when all three indices pick a 4 (8 triples) or all pick the 3 (1 triple): 27 - 9 = 18.
Constraints
1 <= nums.length <= 10000 <= nums[i] < 2^16
Hints for Triples with Bitwise AND Equal To Zero
Hint 1
Three nested loops cost 10^9 steps. Can two of the indices be handled together?
Hint 2
nums[i] AND nums[j]takes at most 2^16 distinct values. Count how often each one occurs over all ordered pairs.Hint 3
Then, for each
nums[k], add the counts of the pair-ANDspwithp AND nums[k] == 0.
How to solve Triples with Bitwise AND Equal To Zero
Split the triple into a pair and a single element: tabulate how many ordered pairs produce each AND value, then match every third element against the table.
Approach
- For every ordered pair
(i, j), incrementcount[nums[i] AND nums[j]], and remember each value the first time it appears. - For every
k, walk the distinct pair-AND valuespand addcount[p]wheneverp AND nums[k] == 0. - Return the sum.
Why it works
Each triple (i, j, k) is counted exactly once: its pair (i, j) lands in the bucket of its AND value p, and that bucket is added for k precisely when p AND nums[k] == 0, which is the triple's condition.
Complexity
- Time —
O(n² + n · d), d = distinct pair ANDs ≤ min(n², 2^16) - Space —
O(2^16)
Pitfalls
- Triples are ordered and indices may repeat —
(0,0,0)counts, and(0,1,2)differs from(2,1,0). - The count can reach 10^9; it still fits a 32-bit signed integer, but only just.
- Scanning all 2^16 values for every
kis correct but much slower than scanning only the values that occur.
Reference solution
Python
from typing import List
def countTriplets(nums: List[int]) -> int:
pairs = {}
for a in nums:
for b in nums:
v = a & b
pairs[v] = pairs.get(v, 0) + 1
items = list(pairs.items())
total = 0
for c in nums:
for v, k in items:
if (v & c) == 0:
total += k
return totalJava
public static int countTriplets(int[] nums) {
int[] cnt = new int[1 << 16];
int[] keys = new int[Math.min(nums.length * nums.length, 1 << 16)];
int nk = 0;
for (int a : nums) {
for (int b : nums) {
int v = a & b;
if (cnt[v]++ == 0) keys[nk++] = v;
}
}
int total = 0;
for (int c : nums) {
for (int t = 0; t < nk; t++) {
if ((keys[t] & c) == 0) total += cnt[keys[t]];
}
}
return total;
}C++
int countTriplets(vector<int>& nums) {
vector<int> cnt(1 << 16, 0);
vector<int> keys;
for (int a : nums) {
for (int b : nums) {
int v = a & b;
if (cnt[v]++ == 0) keys.push_back(v);
}
}
int total = 0;
for (int c : nums) {
for (int v : keys) {
if ((v & c) == 0) total += cnt[v];
}
}
return total;
}JavaScript
var countTriplets = function(nums) {
var cnt = new Map();
for (var i = 0; i < nums.length; i++) {
for (var j = 0; j < nums.length; j++) {
var v = nums[i] & nums[j];
cnt.set(v, (cnt.get(v) || 0) + 1);
}
}
var keys = [], vals = [];
cnt.forEach(function(c, key) { keys.push(key); vals.push(c); });
var total = 0;
for (var k = 0; k < nums.length; k++) {
for (var t = 0; t < keys.length; t++) {
if ((keys[t] & nums[k]) === 0) total += vals[t];
}
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets