Scale Engineer

Triples with Bitwise AND Equal To Zero

Hard
#0936Time: 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.1 company
Patterns
Bit Manipulation
Data structures
ArrayHash Table
Companies
Flipkart

Prompt

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] < 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 count to 0.
  • Use a loop for index i from 0 to n-1, where n is the length of nums.
  • Inside, use a nested loop for index j from 0 to n-1.
  • Inside, use another nested loop for index k from 0 to n-1.
  • In the innermost loop, check if the condition (nums[i] & nums[j] & nums[k]) == 0 is 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).

Solutions

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;  }}

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.

← Previous

Previous problem

Next →

Next problem