#982

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Triples with Bitwise AND Equal To Zero

Count all index triples in an array where the bitwise AND of their elements equals zero using efficient bit manipulation.

array hash table bit manipulation

Problem Statement

Given an integer array nums, determine the number of index triples (i, j, k) where the bitwise AND of nums[i], nums[j], and nums[k] equals zero. Each index can repeat, and all valid combinations must be counted efficiently using bit manipulation techniques.

Constraints: 1 <= nums.length <= 1000 and 0 <= nums[i] < 2^16. Return the total count of AND triples that satisfy nums[i] & nums[j] & nums[k] == 0. For example, nums = [2,1,3] should return 12 as there are twelve valid triples where the AND equals zero.

Examples

Example 1

Input: nums = [2,1,3]

Output: 12

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

Example details omitted.

Constraints

1 <= nums.length <= 1000
0 <= nums[i] < 216

Solution Approach

Brute Force Triple Scan

Iterate over all possible triples (i, j, k) and compute nums[i] & nums[j] & nums[k] for each. Count the number of times it equals zero. This method has O(n^3) time complexity and fails for large arrays due to performance.

Precompute Pairwise ANDs with Hash Map

Generate all pairwise AND results from nums[i] & nums[j] and store their frequency in a hash map. Then iterate through nums[k] and check how many precomputed pairs satisfy AND == 0 with nums[k]. This reduces redundant AND calculations and leverages hash lookup for fast counting.

Bit Mask Optimization

Use the limited value range of nums[i] (< 2^16) to precompute counts for each possible bitmask. Then for each nums[k], enumerate masks that AND to zero and sum their counts. This uses bit manipulation to efficiently handle large arrays within the constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the approach: brute force is O(n^3), hash map pairwise computation is O(n^2 + n*2^16) in worst case, and bitmask optimization leverages the 2^16 bound to stay efficient. Space complexity is O(n^2) for pairwise storage or O(2^16) for bitmask counts.

What Interviewers Usually Probe

Candidate immediately considers the high n^3 brute force and mentions performance issues.
Candidate references bit manipulation and hash tables to reduce redundant computation.
Candidate evaluates value constraints to optimize for possible masks and avoids unnecessary nested loops.

Common Pitfalls or Variants

Common pitfalls

Attempting direct triple nested loops on large arrays, causing TLE.
Forgetting that indices can repeat, leading to undercounting.
Ignoring the 2^16 constraint, missing bitmask-based optimizations.

Follow-up variants

Count quadruples with bitwise AND zero instead of triples.
Return all valid triples instead of just the count.
Modify to count AND triples for a target value other than zero.

FAQ

What is the main pattern used in Triples with Bitwise AND Equal To Zero?

The core pattern is array scanning combined with hash table lookups to efficiently count valid AND triples.

Can indices repeat in valid triples?

Yes, i, j, and k can be the same index, and all combinations must be counted.

Why not just use a triple nested loop?

Triple nested loops have O(n^3) time complexity, which is too slow for arrays up to length 1000.

How does the bitmask optimization improve performance?

It uses the 2^16 value constraint to precompute counts of masks and sum compatible combinations, reducing redundant computation.

What is a common pitfall when implementing this problem?

A frequent mistake is ignoring repeated indices or overcounting pairs without considering zero AND conditions, leading to incorrect totals.

terminal

Solution

Solution 1: Enumeration + Counting

First, we enumerate any two numbers $x$ and $y$, and use a hash table or array $cnt$ to count the occurrences of their bitwise AND result $x \& y$.

1

2

3

4

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)

Continue Practicing

#996 number of squareful arrays #957 prison cells after n days #1177 can make palindrome from substring