Triples with Bitwise AND Equal To Zero
Triples with Bitwise AND Equal To Zero is a hard bit manipulation problem solved with the sum over subsets (sos) dp pattern.
The best approach, optimal (pair and counts + sum over subsets dp), runs in O(n² + 16 · 2^16) time and O(2^16) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (three nested loops) up.
Problem
Given an integer array nums, count the ordered triples of indices (i, j, k) such that nums[i] & nums[j] & nums[k] == 0, where & is bitwise AND.
Each index may be any value in [0, nums.length), independently of the others, so indices are allowed to repeat and different orders of the same indices count separately.
Examples
Example 1
- Input
nums = [1, 2, 4]- Output
24- Why
- There are 3³ = 27 ordered index triples. Only the three that use one value three times ((1,1,1), (2,2,2), (4,4,4)) keep a bit set.
Example 2
- Input
nums = [3, 5, 6]- Output
6- Why
- Any two of these share a bit, so only triples using all three values work: 3 & 5 & 6 = 0, in 3! = 6 orders.
Example 3
- Input
nums = [0]- Output
1- Why
- The single triple (0, 0, 0) uses the same index three times, which is allowed.
Constraints
1 <= nums.length <= 10000 <= nums[i] < 2^16
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (three nested loops) | O(n³) | O(1) |
| Optimal (pair AND counts + sum over subsets DP) | O(n² + 16 · 2^16) | O(2^16) |
1Brute force (three nested loops)
O(n³)n³ ordered triples, each checked in O(1).O(1)Only a counter.Try every ordered triple of indices and count those whose AND is zero.
- For i, j, k in [0, n): if nums[i] & nums[j] & nums[k] == 0, count++.
- Small speed-up: compute a = nums[i] & nums[j] once per pair before the inner loop.
class Solution {
public int countTriplets(int[] nums) {
int n = nums.length, count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
int a = nums[i] & nums[j];
for (int k = 0; k < n; k++)
if ((a & nums[k]) == 0) count++;
}
return count;
}
}class Solution:
def countTriplets(self, nums: List[int]) -> int:
count = 0
for x in nums:
for y in nums:
a = x & y
for z in nums:
if a & z == 0:
count += 1
return countclass Solution {
public:
int countTriplets(vector<int>& nums) {
int n = nums.size(), count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
int a = nums[i] & nums[j];
for (int k = 0; k < n; k++)
if ((a & nums[k]) == 0) count++;
}
return count;
}
};function countTriplets(nums) {
const n = nums.length;
let count = 0;
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++) {
const a = nums[i] & nums[j];
for (let k = 0; k < n; k++)
if ((a & nums[k]) === 0) count++;
}
return count;
}2Optimal (pair AND counts + sum over subsets DP)
O(n² + 16 · 2^16)n² pairs to build the counts (10^6), then 16 passes over 65,536 masks, then one pass over nums.O(2^16)One count array indexed by 16-bit mask.Count every ordered pair by its AND value: cnt[m] = number of (i, j) with nums[i] & nums[j] = m. A third value c works with mask m exactly when m is a subset of c (16 bits). Turn cnt into subset sums with SOS DP, so sub[mask] = total of cnt over all submasks of mask. Then each c contributes sub[c & 0xFFFF].
- cnt = array of size 2^16; for every ordered pair (a, b) of values, cnt[a & b]++.
- SOS DP: for each bit b in 0..15, for each mask m with bit b set, cnt[m] += cnt[m ^ (1 << b)]. Now cnt[m] counts pairs whose AND is a submask of m.
- Answer = sum over c in nums of cnt[~c & (2^16 - 1)].
class Solution {
public int countTriplets(int[] nums) {
final int FULL = 1 << 16;
int[] cnt = new int[FULL];
for (int a : nums)
for (int b : nums) cnt[a & b]++;
for (int bit = 0; bit < 16; bit++)
for (int m = 0; m < FULL; m++)
if ((m & (1 << bit)) != 0) cnt[m] += cnt[m ^ (1 << bit)];
int total = 0;
for (int c : nums) total += cnt[~c & (FULL - 1)];
return total;
}
}class Solution:
def countTriplets(self, nums: List[int]) -> int:
FULL = 1 << 16
cnt = [0] * FULL
for a in nums:
for b in nums:
cnt[a & b] += 1
for bit in range(16):
step = 1 << bit
for m in range(FULL):
if m & step:
cnt[m] += cnt[m ^ step]
return sum(cnt[~c & (FULL - 1)] for c in nums)class Solution {
public:
int countTriplets(vector<int>& nums) {
const int FULL = 1 << 16;
vector<int> cnt(FULL, 0);
for (int a : nums)
for (int b : nums) cnt[a & b]++;
for (int bit = 0; bit < 16; bit++)
for (int m = 0; m < FULL; m++)
if (m & (1 << bit)) cnt[m] += cnt[m ^ (1 << bit)];
int total = 0;
for (int c : nums) total += cnt[~c & (FULL - 1)];
return total;
}
};function countTriplets(nums) {
const FULL = 1 << 16;
const cnt = new Int32Array(FULL);
for (const a of nums)
for (const b of nums) cnt[a & b]++;
for (let bit = 0; bit < 16; bit++)
for (let m = 0; m < FULL; m++)
if (m & (1 << bit)) cnt[m] += cnt[m ^ (1 << bit)];
let total = 0;
for (const c of nums) total += cnt[~c & (FULL - 1)];
return total;
}Edge cases to test
- Indices may repeat: (i, i, i) counts if nums[i] = 0
- Order matters: (i, j, k) and (j, i, k) are different triples
- All values equal and non-zero: answer 0
- Many zeros: the answer can reach n³ = 10^9, which still fits in a 32-bit int
Hints
Hint 1
Three nested loops are n³ = 10^9 for the largest input: too slow.
Hint 2
Values are only 16 bits wide. Precompute how many ordered pairs (i, j) give each AND value; there are at most 2^16 of them.
Hint 3
For a third number c, you need the pair counts over all masks that are a subset of ~c. A sum over subsets for every mask is exactly what SOS (sum over subsets) DP computes in 16 · 2^16 steps.
FAQ
What is the best time complexity for Triples with Bitwise AND Equal To Zero?
Optimal (pair AND counts + sum over subsets DP) runs in O(n² + 16 · 2^16) time and O(2^16) extra space. n² pairs to build the counts (10^6), then 16 passes over 65,536 masks, then one pass over nums.
Which pattern does Triples with Bitwise AND Equal To Zero use?
It is a bit manipulation problem that uses the sum over subsets (sos) dp pattern.
Is there a brute force solution for Triples with Bitwise AND Equal To Zero?
Yes. Brute force (three nested loops) takes O(n³) time and O(1) space. Try every ordered triple of indices and count those whose AND is zero.
Which edge cases should I test for Triples with Bitwise AND Equal To Zero?
Indices may repeat: (i, i, i) counts if nums[i] = 0; Order matters: (i, j, k) and (j, i, k) are different triples; All values equal and non-zero: answer 0; Many zeros: the answer can reach n³ = 10^9, which still fits in a 32-bit int.