Jobs

Interviews

Discussions

Triples with Bitwise AND Equal To Zero

Hard

Flipkart

0 views

Topics:

ArraysBit Manipulation

Given an integer array nums, return the number of AND triples.

An AND triple is a triple of indices (i, j, k) such that:

0 <= i < nums.length
0 <= j < nums.length
0 <= k < nums.length
nums[i] & nums[j] & nums[k] == 0, where & represents the bitwise-AND operator.

Example 1:

Input: nums = [2,1,3]
Output: 12
Explanation: 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

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] < 2¹⁶

Try coding it in LeetCode

Triples with Bitwise AND Equal To Zero

Hard

Flipkart

0 views

Topics:

ArraysBit Manipulation

Given an integer array nums, return the number of AND triples.

An AND triple is a triple of indices (i, j, k) such that:

0 <= i < nums.length
0 <= j < nums.length
0 <= k < nums.length
nums[i] & nums[j] & nums[k] == 0, where & represents the bitwise-AND operator.

Example 1:

Input: nums = [2,1,3]
Output: 12
Explanation: 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

Constraints:

1 <= nums.length <= 1000
0 <= nums[i] < 2¹⁶

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the `nums` array and the maximum value of an element within `nums`?
Can the input array `nums` be empty or null?
Are we looking for unique triples (i, j, k), or is the order significant such that (1,2,3) and (3,2,1) are considered different?
Are duplicate values within the `nums` array allowed, and if so, how do they affect the count of triples?
If no such triples exist that satisfy the condition, what value should I return?

Brute Force Solution

Approach

The brute force strategy for this problem is very straightforward: we simply try every possible combination of three numbers from our given list. We then perform the bitwise AND operation on each combination to see if the result is zero.

Here's how the algorithm would work step-by-step:

Take the first number from the list.
Then, for each number in the list, take it along with the first number.
Now, for each number in the list, take it along with the first two numbers selected in previous steps. You will now have a group of three numbers.
Perform the bitwise AND operation on these three numbers. This is a special operation on the numbers that results in a new number.
Check if the result of this operation is zero. If it is, we have found a valid triple.
Count the number of times this result is zero by repeating the above steps for every possible group of three numbers we can make from the initial list.

Code Implementation

def count_triples_with_bitwise_and_equal_to_zero(numbers):
    count = 0

    # Iterate through all possible combinations of three numbers
    for first_number_index in range(len(numbers)):
        for second_number_index in range(len(numbers)):

            # Iterate through the remaining numbers to form the triple
            for third_number_index in range(len(numbers)):

                # Calculate the bitwise AND of the triple
                bitwise_and_result = numbers[first_number_index] & numbers[second_number_index] & numbers[third_number_index]

                # Check if the bitwise AND is equal to zero
                if bitwise_and_result == 0:
                    count += 1

    # Return the total count of triples that satisfy the condition
    return count

Big(O) Analysis

Time Complexity

O(n^3) – The provided brute force solution iterates through all possible triplets in the input list of size n. It selects the first number in O(1) time. Then, it iterates through all other numbers in O(n) time, and for each of those, it iterates again through all numbers in O(n) time, thus creating a group of three. So, for each of the n numbers initially selected, we have n * n = n^2 operations. This leads to approximately n * n * n = n^3 operations, which simplifies to O(n^3).

Space Complexity

O(1) – The provided brute force approach iterates through the input list to find all possible triples. The algorithm doesn't use any auxiliary data structures like temporary lists or hash maps to store intermediate results. It only uses a constant number of variables to keep track of the indices for the nested loops and the result of the bitwise AND operation. Therefore, the auxiliary space complexity remains constant, regardless of the input size N.

Optimal Solution

Approach

Instead of checking every possible set of three numbers, which would take too long, we'll use a trick based on bitwise operations to speed things up. We'll pre-calculate the possible results of bitwise OR on pairs of numbers and then quickly check if there's a third number that makes the bitwise AND of the three numbers zero.

Here's how the algorithm would work step-by-step:

First, create a list of all possible values we can get by performing a bitwise OR operation on every possible pair of numbers from the input list.
Then, for each number in the input list, check how many of the pre-calculated bitwise OR results, when combined with this number using a bitwise AND, produce a zero.
Count the number of times a combination of three numbers produces a zero result using bitwise AND.
The pre-calculation and then checking speeds things up considerably by skipping many unnecessary checks compared to a brute-force approach.

Code Implementation

def triples_with_bitwise_and_equal_to_zero(numbers):
    count = 0
    or_values = {}

    # Pre-calculate bitwise OR of all pairs of numbers.
    for i in range(len(numbers)):
        for j in range(len(numbers)):
            bitwise_or = numbers[i] | numbers[j]
            or_values[bitwise_or] = or_values.get(bitwise_or, 0) + 1

    # Iterate through each number to find valid triples.
    for number in numbers:
        for bitwise_or, frequency in or_values.items():

            # Check if bitwise AND of current number and precalculated OR is zero.
            if (number & bitwise_or) == 0:
                count += frequency

    # Because we counted (i,j,k) and (j,i,k) we must return
    # the count divided by the double count.
    return count

Big(O) Analysis

Time Complexity

O(n²) – The algorithm first iterates through all possible pairs of numbers from the input list of size n to calculate their bitwise OR. This nested loop results in approximately n * n/2 operations. Then, for each number in the input list (n), it iterates through the pre-calculated bitwise OR results (which has a maximum size proportional to n²), performing a bitwise AND operation. Therefore, the overall time complexity is dominated by the initial pair generation, resulting in O(n²).

Space Complexity

O(N^2) – The algorithm pre-calculates bitwise OR results of all pairs of numbers from the input list of size N. This leads to creating a list to store these results, and in the worst case where all pairs are unique, the list will contain approximately N * N (or N^2) entries. Thus, the auxiliary space required to store the bitwise OR results grows quadratically with the size of the input list. The other variables used take constant space, so the overall space complexity is dominated by the storage of OR results.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the input array is null or empty since no triples can be formed.
Array with fewer than 3 elements	Return 0 if the array has fewer than 3 elements as a triple requires 3 elements.
Array with all elements equal to 0	The bitwise AND of any three zeros is zero, so return n^3 where n is the array length.
Array with elements having all bits set to 1 (e.g., all 255 if using bytes)	The bitwise AND of any three such numbers will also be non-zero (unless there is a 0), potentially leading to a return value of 0 if no triples satisfy the condition.
Integer overflow in the count of triples	Use a 64-bit integer (long) to store the count to prevent potential overflow issues with large arrays.
Large input array (performance considerations)	Optimize the algorithm to avoid brute-force O(n^3) complexity, potentially using frequency counting or bitmasking techniques.
Presence of duplicate numbers in the input array	The algorithm should correctly handle duplicate numbers since the indices (i, j, k) must be distinct within the bounds of the array, not necessarily point to distinct values.
Mix of small and very large numbers (close to Integer.MAX_VALUE)	Bitwise AND operations should still work correctly with a mix of small and large integers within the allowed range, and potential bit patterns should be examined.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the `nums` array and the maximum value of an element within `nums`?
Can the input array `nums` be empty or null?
Are we looking for unique triples (i, j, k), or is the order significant such that (1,2,3) and (3,2,1) are considered different?
Are duplicate values within the `nums` array allowed, and if so, how do they affect the count of triples?
If no such triples exist that satisfy the condition, what value should I return?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first number from the list.
Then, for each number in the list, take it along with the first number.
Now, for each number in the list, take it along with the first two numbers selected in previous steps. You will now have a group of three numbers.
Perform the bitwise AND operation on these three numbers. This is a special operation on the numbers that results in a new number.
Check if the result of this operation is zero. If it is, we have found a valid triple.
Count the number of times this result is zero by repeating the above steps for every possible group of three numbers we can make from the initial list.

Code Implementation

def count_triples_with_bitwise_and_equal_to_zero(numbers):
    count = 0

    # Iterate through all possible combinations of three numbers
    for first_number_index in range(len(numbers)):
        for second_number_index in range(len(numbers)):

            # Iterate through the remaining numbers to form the triple
            for third_number_index in range(len(numbers)):

                # Calculate the bitwise AND of the triple
                bitwise_and_result = numbers[first_number_index] & numbers[second_number_index] & numbers[third_number_index]

                # Check if the bitwise AND is equal to zero
                if bitwise_and_result == 0:
                    count += 1

    # Return the total count of triples that satisfy the condition
    return count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, create a list of all possible values we can get by performing a bitwise OR operation on every possible pair of numbers from the input list.
Then, for each number in the input list, check how many of the pre-calculated bitwise OR results, when combined with this number using a bitwise AND, produce a zero.
Count the number of times a combination of three numbers produces a zero result using bitwise AND.
The pre-calculation and then checking speeds things up considerably by skipping many unnecessary checks compared to a brute-force approach.

Code Implementation

def triples_with_bitwise_and_equal_to_zero(numbers):
    count = 0
    or_values = {}

    # Pre-calculate bitwise OR of all pairs of numbers.
    for i in range(len(numbers)):
        for j in range(len(numbers)):
            bitwise_or = numbers[i] | numbers[j]
            or_values[bitwise_or] = or_values.get(bitwise_or, 0) + 1

    # Iterate through each number to find valid triples.
    for number in numbers:
        for bitwise_or, frequency in or_values.items():

            # Check if bitwise AND of current number and precalculated OR is zero.
            if (number & bitwise_or) == 0:
                count += frequency

    # Because we counted (i,j,k) and (j,i,k) we must return
    # the count divided by the double count.
    return count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the input array is null or empty since no triples can be formed.
Array with fewer than 3 elements	Return 0 if the array has fewer than 3 elements as a triple requires 3 elements.
Array with all elements equal to 0	The bitwise AND of any three zeros is zero, so return n^3 where n is the array length.
Array with elements having all bits set to 1 (e.g., all 255 if using bytes)	The bitwise AND of any three such numbers will also be non-zero (unless there is a 0), potentially leading to a return value of 0 if no triples satisfy the condition.
Integer overflow in the count of triples	Use a 64-bit integer (long) to store the count to prevent potential overflow issues with large arrays.
Large input array (performance considerations)	Optimize the algorithm to avoid brute-force O(n^3) complexity, potentially using frequency counting or bitmasking techniques.
Presence of duplicate numbers in the input array	The algorithm should correctly handle duplicate numbers since the indices (i, j, k) must be distinct within the bounds of the array, not necessarily point to distinct values.
Mix of small and very large numbers (close to Integer.MAX_VALUE)	Bitwise AND operations should still work correctly with a mix of small and large integers within the allowed range, and potential bit patterns should be examined.