We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Triples with Bitwise AND Equal To Zero

Number: 1024

Difficulty: Hard

Paid? No

Companies: Flipkart

Problem Description

Given an integer array nums, count the number of triples (i, j, k) such that:

  • 0 <= i, j, k < nums.length
  • nums[i] & nums[j] & nums[k] == 0 (where & denotes the bitwise-AND operator).

Key Insights

  • A straightforward triple nested loop yields O(n^3) time complexity, which is impractical for n up to 1000.
  • Use a frequency map to record occurrences of each number, reducing duplicate computations.
  • Precompute the frequency of every possible pairwise AND result between numbers.
  • For every fixed number (as the third element), sum over all pairs whose AND with this number equals 0.
  • This approach avoids iterating over all triples explicitly and leverages bitwise operations for speed.

Space and Time Complexity

Time Complexity: O(U^2 + U) where U is the number of unique numbers (worst-case U can be near n, but typically much less), combined with bit-level operations. Space Complexity: O(2^(bits)) for the auxiliary frequency map and pairwise results, though practically it is bounded by the number of unique numbers.

Solution

We use a frequency map to count occurrences of each number in nums. Then, we precompute a dictionary (or map) holding the count of all pairwise AND results (treating pairs as ordered, which is valid for the problem). Finally, for each distinct number (the third element), we check which pair AND results, when AND-ed with this number, yield 0. Multiplying the counts from the pair dictionary and this number’s frequency gives the number of valid triples.

Code Solutions

def countTriplets(nums):
    # Build frequency map for numbers in nums
    frequency = {}
    for num in nums:
        frequency[num] = frequency.get(num, 0) + 1

    # Precompute count of pairwise AND outcomes.
    and_dict = {}
    unique_nums = list(frequency.keys())
    # Iterate over all ordered pairs
    for i in range(len(unique_nums)):
        num1 = unique_nums[i]
        for j in range(len(unique_nums)):
            num2 = unique_nums[j]
            result = num1 & num2
            # Count the number of pairs that yield 'result'
            and_dict[result] = and_dict.get(result, 0) + frequency[num1] * frequency[num2]

    count_triples = 0
    # For every possible third element, accumulate count if AND condition holds
    for num in unique_nums:
        for key, count in and_dict.items():
            if (key & num) == 0:
                count_triples += count * frequency[num]
    return count_triples

# Example usage:
print(countTriplets([2, 1, 3]))  # Expected output: 12
print(countTriplets([0, 0, 0]))  # Expected output: 27
← Back to All Questions