Triples with Bitwise AND Equal To Zero

Hard
1328.

Triples with Bitwise AND Equal To Zero

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.

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 <= 1000
  • 0 <= nums[i] < 2^16
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var countTriplets = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 1000
  • 0 <= nums[i] < 2^16

Hints for Triples with Bitwise AND Equal To Zero

  1. Hint 1

    Three nested loops cost 10^9 steps. Can two of the indices be handled together?

  2. Hint 2

    nums[i] AND nums[j] takes at most 2^16 distinct values. Count how often each one occurs over all ordered pairs.

  3. Hint 3

    Then, for each nums[k], add the counts of the pair-ANDs p with p 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

  1. For every ordered pair (i, j), increment count[nums[i] AND nums[j]], and remember each value the first time it appears.
  2. For every k, walk the distinct pair-AND values p and add count[p] whenever p AND nums[k] == 0.
  3. 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 k is 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 total

Java

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