Triples with Bitwise AND Equal To Zero Solution in C++

Problem Description

Ah, the classic “Triples with Bitwise AND Equal To Zero” problem! It’s like trying to find three friends who can agree on a movie to watch without arguing about it. We’re looking for three numbers from an array that, when combined using the bitwise AND operation, result in zero.

Imagine you’re at a party, and you want to find three people who can all agree on the same snack without any of them being allergic to it. If one of them is allergic to peanuts, and the other two are munching on peanut butter cookies, well, that’s a recipe for disaster! Similarly, in our problem, we want to find triplets such that their bitwise AND is zero.

Code Solution


class Solution {
 public:
  int countTriplets(vector& nums) {
    constexpr int kMax = 1 << 16;
    int ans = 0;
    vector count(kMax);  // {nums[i] & nums[j]: times}

    for (const int a : nums)
      for (const int b : nums)
        ++count[a & b];

    for (const int num : nums)
      for (int i = 0; i < kMax; ++i)
        if ((num & i) == 0)
          ans += count[i];

    return ans;
  }
};

Approach

The approach taken in this solution is quite clever. It first calculates how many times each possible bitwise AND result occurs between pairs of numbers in the input array. This is stored in the count vector. Then, for each number in the array, it checks how many of these results can combine with the current number to yield zero when ANDed together. If they do, it adds the count of those results to the answer.

In simpler terms, it’s like creating a guest list of all possible snack combinations and then checking how many of those combinations can be enjoyed without any allergies!

Time and Space Complexity

Time Complexity

O(N² + N * K), where N is the number of elements in the input array and K is the maximum value of the bitwise AND results. The first part (O(N²)) comes from the nested loops to calculate the counts, and the second part (O(N * K)) comes from checking each number against all possible AND results.

Space Complexity

O(K), where K is the maximum value of the bitwise AND results stored in the count vector.

Real-World Example

Let’s say you’re organizing a game night with your friends. You want to pick three games that everyone can play together without any arguments about the rules. If one game requires a board and another requires a console, and your third friend only has a deck of cards, you’re going to have a tough time finding a game that suits everyone. Similarly, in our problem, we’re looking for three numbers that can “play nice” together under the bitwise AND operation to yield zero.