982. Triples with Bitwise AND Equal To Zero

HardBit ManipulationArrayHash Table
Leetcode Link

Problem Description

Given an array of integers nums, we are tasked with finding the count of all unique "AND triples." An "AND triple" is defined as a combination of three indices (i, j, k) within the bounds of the array nums such that the following conditions are met:

  • 0 <= i < nums.length
  • 0 <= j < nums.length
  • 0 <= k < nums.length

The key condition for an "AND triple" is that the bitwise AND operation (&) applied to nums[i], nums[j], and nums[k] results in zero, i.e., nums[i] & nums[j] & nums[k] == 0.

The bitwise AND operation takes two numbers as operands and performs the AND operation on every pair of corresponding bits. The operation results in a 1 in each bit position for which the corresponding bits of both operands are 1s.

The goal is to write a function that will return the total number of such "AND triples."

Intuition

To solve the problem efficiently, we focus on the definition of the bitwise AND operator. When performing an AND operation where the result is 0, any bit in the resulting number must have been 0 in at least one of the operands. This means that as long as there is a zero at the same position in either i, j, or k index of nums, their AND operation will yield a zero.

An intuitive approach might be trying all possible triples (i, j, k) and checking their AND operation one by one, but this would result in a time complexity of O(n^3), which is not efficient for large arrays.

Instead, we can take advantage of the commutative property of the AND operation (i.e., a & b = b & a) and count the number of occurrences for every possible result of nums[i] & nums[j]. We can precompute and store these counts in a Counter dictionary, which is a type of dictionary provided by Python's collections module that counts the occurrences of each element.

After counting all the possible AND results of pairs (i, j), we iterate through each value z in nums and for each pair (xy, v) in our Counter dictionary (where xy is a result of nums[i] & nums[j] and v is the count of how many times this result occurred). If xy & z == 0, it means this z paired with all v occurrences of xy will contribute v to the total count of "AND triples".

This approach significantly reduces the complexity of the problem by reducing the three-dimensional problem (checking all triples) into a two-dimensional problem (storing pairs) and then iterating through the array only once more, giving us an overall time complexity closer to O(n^2).

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Solution Approach

The solution employs an efficient approach that involves a combination of precomputation and hash mapping through the Counter class, which is part of Python's collections module. The idea is to leverage the properties of the bitwise AND operation to reduce the computational complexity. Here's a breakdown of the implementation steps using the provided solution code:

  1. Precomputation of Pairwise AND results: We create a Counter to precompute and store all possible bitwise AND results x & y for each pair in the array nums. This precomputation is done in a nested loop where x and y iterate over all elements in nums.

    1cnt = Counter(x & y for x in nums for y in nums)

    cnt now holds the frequency of each result that can be obtained by performing the bitwise AND operation on any two elements in nums.

  2. Iterate Through the Counter and the Array: We iterate through both the Counter dictionary cnt and the array nums. For every combination of xy (a precomputed AND result from cnt) and z (an element in nums), we check if the bitwise AND of xy & z equals 0.

    1return sum(v for xy, v in cnt.items() for z in nums if xy & z == 0)

    In this line of code, xy represents a possible result of nums[i] & nums[j] and v is the number of times this result occurs (the count). We are interested in the cases where xy & z is zero because that means we've found a valid "AND triple".

In the above implementation, the complex part of the problem, which is finding pairs whose AND is 0, is handled by the Counter, which amortizes that work over all element pairs with a single pass through nums. Then, the final loop provides a multiplication factor (v) for each zero-resulting AND pair when checked against all elements of nums. This clever use of hash mapping paired with the bitwise operation properties results in an elegant solution that is more computationally efficient than brute force.

Data Structures:

  • Counter (hash map): A specialized dictionary for counting hashable objects, quite handy for counting occurrences of results (precomputed AND operations).

Algorithm Patterns:

  • Hash mapping: To store and access the count of occurrences of pairwise AND results efficiently.
  • Bitwise operations: Core part of the logic, determining the property of the "AND triple".

Complexity Analysis:

  • Time Complexity: O(n^2), since we iterate over all pairs once to compute the AND results and store them in the Counter, and then iterate over this Counter and nums in a nested fashion.
  • Space Complexity: O(n^2), primarily due to the space required to store the Counter dictionary, which in the worst case could hold a distinct count for every pair combination.
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Example Walkthrough

Let's consider a small array nums = [2, 1, 4] to illustrate the solution approach:

  1. Precomputation of Pairwise AND results:

    • We will calculate the bitwise AND for every pair of numbers in the array and count the occurrences of each result. For our example array nums, the pairs and their AND results are:
      • 2 & 2 = 2
      • 2 & 1 = 0 (since the binary representation of 2 is 10 and 1 is 01, the AND operation results in 00)
      • 2 & 4 = 0 (binary 10 AND 100 results in 000)
      • 1 & 1 = 1
      • 1 & 4 = 0 (binary 01 AND 100 results in 000)
      • 4 & 4 = 4
    • The frequency of AND results will then be stored in a Counter: cnt becomes {2: 1, 0: 3, 1: 1, 4: 1}.

  2. Iterate Through the Counter and the Array:

    • With the Counter ready, we now iterate through each unique AND result stored in cnt and each element z in nums, and count if the AND of the stored result with z equals 0:
      • For xy = 2: The AND operation with any of nums does not yield 0, so no count is added.
      • For xy = 0: The AND operation with all elements in nums (2, 1, 4) will yield 0, and since cnt[0] = 3, we have 3 valid "AND triples" for each element in nums, totaling 9.
      • For xy = 1: The AND operation with all elements in nums (2, 1, 4) does not yield 0, so no count is added.
      • For xy = 4: The AND operation with any of nums does not yield 0, so no count is added.
    • The count for this iteration will be 0 + 9 + 0 + 0 = 9.

Therefore, the total count of all unique "AND triples" for the array nums = [2, 1, 4] is 9.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def countTriplets(self, nums: List[int]) -> int:
5        # Create a counter (dictionary) to store the frequency of each bitwise AND result.
6        # We calculate bitwise AND for all possible pairs of numbers in the nums list.
7        frequency_counter = Counter(x & y for x in nums for y in nums)
8      
9        # Initialize a result variable to store the count of triplets.
10        triplet_count = 0
11      
12        # Iterate through the items in the frequency counter. Each item is a tuple (bitwise result, frequency).
13        for bitwise_result, frequency in frequency_counter.items():
14            # For each bitwise AND result, we check if there's a number z in nums such that
15            # bitwise_result & z is equal to 0. If yes, we add the frequency of the bitwise result
16            # to the triplet_count since each occurrence contributes to a valid triplet.
17            for z in nums:
18                if bitwise_result & z == 0:
19                    triplet_count += frequency
20      
21        # After iterating through all items and nums, we return the count of triplets.
22        return triplet_count
23
1class Solution {
2    // Counts the triplets (x, y, z) such that (x & y & z) == 0 from the given nums array.
3    public int countTriplets(int[] nums) {
4        // Find the maximum value in nums to determine the size of the count array.
5        int maxVal = 0;
6        for (int num : nums) {
7            maxVal = Math.max(maxVal, num);
8        }
9      
10        // Initialize the count array that will hold the frequency of occurrences of x & y.
11        int[] count = new int[maxVal + 1];
12        for (int x : nums) {
13            for (int y : nums) {
14                // Increment the count of x & y.
15                count[x & y]++;
16            }
17        }
18      
19        // Initialize the answer to count the number of valid triplets.
20        int answer = 0;
21        // Iterate over all possible combinations of x & y and check with each z in nums.
22        for (int xy = 0; xy <= maxVal; ++xy) {
23            for (int z : nums) {
24                // If x & y & z == 0, add the count of x & y to answer.
25                if ((xy & z) == 0) {
26                    answer += count[xy];
27                }
28            }
29        }
30      
31        // Return the total count of valid triplets.
32        return answer;
33    }
34}
35
1#include <vector>
2#include <algorithm>
3#include <cstring>
4
5class Solution {
6public:
7    // Function to count the number of triplets (x, y, z) from the nums array such that
8    // x & y & z == 0, where & is the bitwise AND operator.
9    int countTriplets(vector<int>& nums) {
10        // Find the maximum element to determine the size of the count array.
11        int maxElement = *max_element(nums.begin(), nums.end());
12      
13        // Create and initialize the count array to store the frequency
14        // of bitwise AND results of all possible pairs (x, y).
15        int count[maxElement + 1];
16        memset(count, 0, sizeof(count));
17      
18        // Populate the count array with the frequency of all possible (x & y) results.
19        for (int x : nums) {
20            for (int y : nums) {
21                count[x & y]++;
22            }
23        }
24      
25        // Initialize the answer to count the number of valid triplets.
26        int answer = 0;
27      
28        // Iterate over all possible values of (x & y) and every element z in nums.
29        for (int xy = 0; xy <= maxElement; ++xy) {
30            for (int z : nums) {
31                // Check if the current combination satisfies x & y & z == 0.
32                // If so, add the frequency of (x & y) to the answer.
33                if ((xy & z) == 0) {
34                    answer += count[xy];
35                }
36            }
37        }
38
39        // Return the total count of valid triplets.
40        return answer;
41    }
42};
43
1function countTriplets(nums: number[]): number {
2    // Find the maximum number in the 'nums' array.
3    const maxNum = Math.max(...nums);
4    // Create an array to store the count of all possible 'x & y' results.
5    const count: number[] = Array(maxNum + 1).fill(0);
6
7    // Calculate the frequency of each 'x & y' result.
8    for (const x of nums) {
9        for (const y of nums) {
10            count[x & y]++;
11        }
12    }
13
14    // Initialize a variable to store the total count of triplets.
15    let tripletCount = 0;
16
17    // Iterate through all possible 'x & y' results.
18    for (let xy = 0; xy <= maxNum; ++xy) {
19        // For each element 'z' in 'nums',
20        // if 'xy & z' is zero, increment the total count of triplets by the pre-calculated frequency of 'xy'.
21        for (const z of nums) {
22            if ((xy & z) === 0) {
23                tripletCount += count[xy];
24            }
25        }
26    }
27
28    // Return the total count of triplets.
29    return tripletCount;
30}
31
Not Sure What to Study? Take the 2-min Quiz：

What's the relationship between a tree and a graph?

Time and Space Complexity

Time Complexity

The time complexity of the provided code can be analyzed by breaking down the nested loops and operations:

  • There are two nested loops that iterate over the array nums to compute bitwise AND (&) for every pair of elements. If n is the length of nums, this results in n^2 iterations.
  • For each iteration, the bitwise AND operation is performed once, which takes constant time, so the nested loops contribute O(n^2) to the time complexity.
  • The count (cnt) is updated during these iterations, which, in the worst case, will store n^2 unique values if all possible AND operations result in unique values. Each update to the Counter (a form of dictionary) takes an average of O(1) time.
  • The final loop iterates v times over the elements z in nums for each xy key-value pair in cnt. If v represents the count of occurrences of xy, and there are m such unique xy pairs (with m being at most n^2), the final loop could iterate up to m * n times.
  • The bitwise AND operation and comparison inside the final loop also take constant time.

Based on the information above, the total time complexity of this code is O(n^2) + O(m * n), which simplifies to O(n^2) because m is at most n^2, and therefore m * n is at most n^3, which is dominated by the n^2 term when n is large.

Space Complexity

For space complexity, we consider the additional space used apart from the input:

  • The Counter object (cnt) holds the result of bitwise AND operations for each pair of elements in nums, which can grow up to n^2 unique key-value pairs in the worst case. Hence, space complexity due to cnt is O(n^2).
  • No other significant additional space is used that grows with the input size.

Thus, the overall space complexity of the code is O(n^2).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the most two important steps in writing a depth first search function? (Select 2)

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫