Triples with Bitwise AND Equal To Zero
HardPrompt
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 & 2Example 2:
Input: nums = [0,0,0]
Output: 27
Constraints:
1 <= nums.length <= 10000 <= nums[i] < 216
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward solution is to check every possible triple of indices (i, j, k). We can use three nested loops, each iterating from 0 to nums.length - 1. Inside the innermost loop, we calculate the bitwise AND of nums[i], nums[j], and nums[k]. If the result is zero, we increment a counter.
Algorithm
- Initialize a counter
countto 0. - Use a loop for index
ifrom 0 ton-1, wherenis the length ofnums. - Inside, use a nested loop for index
jfrom 0 ton-1. - Inside, use another nested loop for index
kfrom 0 ton-1. - In the innermost loop, check if the condition
(nums[i] & nums[j] & nums[k]) == 0is true. - If the condition holds, increment the
count. - After all loops complete, return the final
count.
Walkthrough
This approach directly translates the problem statement into code. It iterates through all combinations of three elements from the array nums (with replacement, as indices can be the same) and checks if their bitwise AND is zero. While simple, its performance degrades rapidly as the size of the input array increases.
class Solution { public int countTriplets(int[] nums) { int n = nums.length; int count = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { if ((nums[i] & nums[j] & nums[k]) == 0) { count++; } } } } return count; }}Complexity
Time
O(N^3), where N is the length of the `nums` array. For each of the N choices for `i`, we have N choices for `j` and N choices for `k`, leading to N*N*N operations.
Space
O(1), as we only use a constant amount of extra space for the counter and loop variables.
Trade-offs
Pros
Very simple to understand and implement.
Requires no extra space besides a few variables.
Cons
Extremely inefficient due to its cubic time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints (N up to 1000).
We can optimize the brute-force approach by reducing one level of iteration. The condition nums[i] & nums[j] & nums[k] == 0 can be rewritten as (nums[i] & nums[j]) & nums[k] == 0. This suggests we can pre-calculate the results of nums[i] & nums[j] for all N*N pairs and store their frequencies. Then, for each element nums[k], we can efficiently find how many of these pre-calculated pairs satisfy the condition.
Algorithm
- Since the maximum value in
numsis less than 2^16, we can use an arraycountsof size 2^16, initialized to zeros. - Iterate through each number
xinnums. - Inside, iterate through each number
yinnums. - Calculate the pairwise AND:
val = x & y. - Increment
counts[val]to store the frequency of this result. - Initialize a result variable
totalTriplesto 0. - Iterate through each number
zinnums. - For each
z, iterate through all possible valuesvfrom 0 to2^16 - 1. - If
(v & z) == 0, it means any pair(i, j)whose AND result wasvwill form a valid triple withz. Addcounts[v]tototalTriples. - Return
totalTriples.
Walkthrough
First, we compute all N*N pairwise ANDs, val = nums[i] & nums[j]. We store the frequency of each resulting value val in an array. Since the maximum value of a number in nums is less than 2^16, the result of the AND operation will also be in this range. Thus, we can use an array counts of size 2^16 for this purpose, where counts[v] stores the number of pairs (i, j) such that nums[i] & nums[j] == v.
After populating the counts array, we iterate through each number z in nums. For each z, we need to find the number of pairs (i, j) such that (nums[i] & nums[j]) & z == 0. This means we must sum up counts[v] for all v where v & z == 0. We can do this by iterating through all possible values v from 0 to 2^16 - 1 and checking the condition.
class Solution { public int countTriplets(int[] nums) { int maxVal = 1 << 16; int[] counts = new int[maxVal]; for (int x : nums) { for (int y : nums) { counts[x & y]++; } } int totalTriples = 0; for (int z : nums) { for (int v = 0; v < maxVal; v++) { if ((z & v) == 0) { totalTriples += counts[v]; } } } return totalTriples; }}Complexity
Time
O(N^2 + N*M), where N is `nums.length` and M is the range of values (2^16). Populating `counts` takes O(N^2). The final calculation takes O(N * M).
Space
O(M), where M is the maximum possible value (2^16). This is for the `counts` array.
Trade-offs
Pros
Significantly more efficient than the brute-force method.
Passes the time limits for the given constraints.
Cons
Requires a large amount of memory for the
countsarray (O(2^16)).The final counting step involves nested loops, one over
numsand one over the entire value range, which can still be time-consuming.
This approach enhances the previous one by significantly optimizing the final counting step. After calculating the frequencies of pairwise ANDs (counts[v]), we need to compute sum(counts[v]) for all v where v & z == 0 for each z in nums. The condition v & z == 0 is equivalent to v being a submask of ~z (the bitwise complement of z). Instead of re-calculating this sum for each z, we can pre-process the counts array using a technique called Sum over Subsets (SOS) Dynamic Programming.
Algorithm
- Initialize an array
dpof sizeM = 2^16with zeros. - Populate
dpwith frequencies of pairwise ANDs: for each pair(x, y)fromnums, incrementdp[x & y]. This takes O(N^2). - Apply Sum over Subsets DP on the
dparray to transform it. For each bitifrom 0 to 15, and for eachmaskfrom 0 toM-1, if thei-th bit ofmaskis set, updatedp[mask] += dp[mask ^ (1 << i)]. - After this O(M log M) transformation,
dp[mask]will hold the sum of initial counts for all submasks ofmask. - Initialize
totalTriples = 0. - For each number
zinnums:- We need pairs
(i, j)where(nums[i] & nums[j])is a submask of the complement ofz. - Calculate the complement:
complement = z ^ (M - 1). - The number of such pairs is already computed as
dp[complement]. - Add
dp[complement]tototalTriples.
- We need pairs
- Return
totalTriples.
Walkthrough
The core idea is to transform the frequency array (let's call it dp) so that dp[mask] stores the sum of frequencies of all its submasks. That is, dp[mask] = sum(counts[submask]) for all submask where submask is a submask of mask. This transformation can be done efficiently in O(M log M) time, where M is the value range (2^16).
Once we have this transformed dp array, finding the answer is straightforward. For each number z in nums, the number of pairs (i, j) satisfying (nums[i] & nums[j]) & z == 0 is the sum of frequencies of all values that are submasks of z's complement. This sum is exactly dp[complement], where complement is the bitwise complement of z. We can sum these values for all z in nums to get the final answer.
class Solution { public int countTriplets(int[] nums) { int maxVal = 1 << 16; int[] dp = new int[maxVal]; // Step 1: Count frequencies of pairwise ANDs for (int x : nums) { for (int y : nums) { dp[x & y]++; } } // Step 2: Apply Sum over Subsets DP for (int i = 0; i < 16; i++) { for (int mask = 0; mask < maxVal; mask++) { if (((mask >> i) & 1) != 0) { dp[mask] += dp[mask ^ (1 << i)]; } } } // Step 3: Calculate the total count of triplets int count = 0; int allOnes = maxVal - 1; for (int z : nums) { // We need (val & z) == 0, which means val is a submask of ~z int complement = z ^ allOnes; count += dp[complement]; } return count; }}Complexity
Time
O(N^2 + M log M), where N is `nums.length` and M is 2^16. O(N^2) for populating `dp`, O(M log M) for the SOS DP transformation, and O(N) for the final summation. This is faster than the O(N*M) term in the previous approach.
Space
O(M), where M is 2^16. This space is used for the `dp` array.
Trade-offs
Pros
Optimal time complexity for the given constraints.
Efficiently reuses computations through dynamic programming.
Cons
The concept of Sum over Subsets DP is more complex and less intuitive.
Still requires O(M) space, which is a large constant.
Solutions
Solution
class Solution {public int countTriplets(int[] nums) { int mx = 0; for (int x : nums) { mx = Math.max(mx, x); } int[] cnt = new int[mx + 1]; for (int x : nums) { for (int y : nums) { cnt[x & y]++; } } int ans = 0; for (int xy = 0; xy <= mx; ++xy) { for (int z : nums) { if ((xy & z) == 0) { ans += cnt[xy]; } } } return ans; }}class Solution {public: int countTriplets(vector<int> &nums) { int mx = *max_element(nums.begin(), nums.end()); int cnt[mx + 1]; memset(cnt, 0, sizeof cnt); for (int &x : nums) { for (int &y : nums) { cnt[x & y]++; } } int ans = 0; for (int xy = 0; xy <= mx; ++xy) { for (int &z : nums) { if ((xy & z) == 0) { ans += cnt[xy]; } } } return ans; }};class Solution : def countTriplets ( self , nums : List [ int ]) -> int : cnt = Counter ( x & y for x in nums for y in nums ) return sum ( v for xy , v in cnt . items () for z in nums if xy & z == 0 )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.