Triples with Bitwise AND Equal To Zero - Practice Coding Problems

Triples with Bitwise AND Equal To Zero - 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.length
0 <= j < nums.length
0 <= k < nums.length
nums[i] & nums[j] & nums[k] == 0, where & represents the bitwise-AND operator.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,1,3]

› Output: 12

💡 Note: The 12 triples with bitwise AND equal to 0 are: (0,0,1), (0,1,0), (0,1,1), (0,1,2), (1,0,0), (1,0,2), (1,1,0), (1,2,0), (1,2,1), (1,2,2), (2,1,0), (2,1,1)

Example 2 — All Zeros

$ Input: nums = [0,0,0]

› Output: 27

💡 Note: All possible 3³ = 27 triples have AND equal to 0 since 0 & 0 & 0 = 0

Example 3 — No Valid Triples

$ Input: nums = [7,7,7]

› Output: 0

💡 Note: 7 & 7 & 7 = 7 ≠ 0, so no triples satisfy the condition

Constraints

1 ≤ nums.length ≤ 1000
0 ≤ nums[i] < 2¹⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array with integer values having different bit patterns

Process

Check all possible triples (i,j,k) for bitwise AND = 0

Output

Count of valid triples

Key Takeaway

🎯 Key Insight: Use bitwise AND properties to find combinations where all bits are covered by at least one zero across the three numbers

Asked in

G Google 15 f Facebook 12 M Microsoft 8

The key insight is that we need to count all possible triples (i,j,k) where the bitwise AND of nums[i] & nums[j] & nums[k] equals zero. The brute force approach uses three nested loops to check all combinations in O(n³) time. An optimized approach precomputes pairwise AND results to reduce redundant calculations, but still maintains O(n³) time complexity overall. Time: O(n³), Space: O(1) for brute force.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Triple Nested Loop	O(n³)	O(1)	Check all possible triples (i,j,k) with three nested loops
Optimized with Pairwise Precomputation	O(n³)	O(n²)	Precompute pairwise AND results, then find third elements efficiently

Brute Force Triple Nested Loop — Algorithm Steps

Step 1: Use three nested loops for indices i, j, k
Step 2: For each triple, compute nums[i] & nums[j] & nums[k]
Step 3: Count triples where the result equals 0

Visualization

Tap to expand

Step-by-Step Walkthrough

Triple Loop

Generate all possible (i,j,k) combinations

AND Check

Compute nums[i] & nums[j] & nums[k]

Count

Increment counter if result equals 0

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(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() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops each iterating n times

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables for counting and iteration

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Triple Nested Loop — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler