Count Triplets with Even XOR Set Bits I

Easy

Amazon

3 views

Topics:

ArraysBit Manipulation

You are given a 0-indexed array of positive integers nums.

You need to find the number of triplets (i, j, k) such that i < j < k and nums[i] ^ nums[j] ^ nums[k] has an even number of set bits.

For example, the integer 21 has 3 set bits.

Return the number of triplets (i, j, k) that meet the conditions.

Example 1:

Input: nums = [2,1,3]
Output: 1
Explanation: The triplets that meet the conditions are:
- (0, 1, 2) -> nums[0] ^ nums[1] ^ nums[2] = 2 ^ 1 ^ 3 = 0 which has 0 set bits, an even number.

Example 2:

Input: nums = [5,1,7,3,9]
Output: 4
Explanation: The triplets that meet the conditions are:
- (0, 1, 2) -> nums[0] ^ nums[1] ^ nums[2] = 5 ^ 1 ^ 7 = 2 which has 1 set bits, an odd number.
- (0, 1, 3) -> nums[0] ^ nums[1] ^ nums[3] = 5 ^ 1 ^ 3 = 7 which has 3 set bits, an odd number.
- (0, 1, 4) -> nums[0] ^ nums[1] ^ nums[4] = 5 ^ 1 ^ 9 = 13 which has 3 set bits, an odd number.
- (0, 2, 3) -> nums[0] ^ nums[2] ^ nums[3] = 5 ^ 7 ^ 3 = 5 which has 2 set bits, an even number.
- (0, 2, 4) -> nums[0] ^ nums[2] ^ nums[4] = 5 ^ 7 ^ 9 = 3 which has 2 set bits, an even number.
- (0, 3, 4) -> nums[0] ^ nums[3] ^ nums[4] = 5 ^ 3 ^ 9 = 7 which has 3 set bits, an odd number.
- (1, 2, 3) -> nums[1] ^ nums[2] ^ nums[3] = 1 ^ 7 ^ 3 = 6 which has 2 set bits, an even number.
- (1, 2, 4) -> nums[1] ^ nums[2] ^ nums[4] = 1 ^ 7 ^ 9 = 15 which has 4 set bits, an even number.
- (1, 3, 4) -> nums[1] ^ nums[3] ^ nums[4] = 1 ^ 3 ^ 9 = 11 which has 3 set bits, an odd number.
- (2, 3, 4) -> nums[2] ^ nums[3] ^ nums[4] = 7 ^ 3 ^ 9 = 5 which has 2 set bits, an even number.
So the answer is 4.

Constraints:

3 <= nums.length <= 1000
1 <= nums[i] <= 10⁸

Count Triplets with Even XOR Set Bits I

Easy

Amazon

3 views

Topics:

ArraysBit Manipulation

You are given a 0-indexed array of positive integers nums.

You need to find the number of triplets (i, j, k) such that i < j < k and nums[i] ^ nums[j] ^ nums[k] has an even number of set bits.

For example, the integer 21 has 3 set bits.

Return the number of triplets (i, j, k) that meet the conditions.

Example 1:

Input: nums = [2,1,3]
Output: 1
Explanation: The triplets that meet the conditions are:
- (0, 1, 2) -> nums[0] ^ nums[1] ^ nums[2] = 2 ^ 1 ^ 3 = 0 which has 0 set bits, an even number.

Example 2:

Input: nums = [5,1,7,3,9]
Output: 4
Explanation: The triplets that meet the conditions are:
- (0, 1, 2) -> nums[0] ^ nums[1] ^ nums[2] = 5 ^ 1 ^ 7 = 2 which has 1 set bits, an odd number.
- (0, 1, 3) -> nums[0] ^ nums[1] ^ nums[3] = 5 ^ 1 ^ 3 = 7 which has 3 set bits, an odd number.
- (0, 1, 4) -> nums[0] ^ nums[1] ^ nums[4] = 5 ^ 1 ^ 9 = 13 which has 3 set bits, an odd number.
- (0, 2, 3) -> nums[0] ^ nums[2] ^ nums[3] = 5 ^ 7 ^ 3 = 5 which has 2 set bits, an even number.
- (0, 2, 4) -> nums[0] ^ nums[2] ^ nums[4] = 5 ^ 7 ^ 9 = 3 which has 2 set bits, an even number.
- (0, 3, 4) -> nums[0] ^ nums[3] ^ nums[4] = 5 ^ 3 ^ 9 = 7 which has 3 set bits, an odd number.
- (1, 2, 3) -> nums[1] ^ nums[2] ^ nums[3] = 1 ^ 7 ^ 3 = 6 which has 2 set bits, an even number.
- (1, 2, 4) -> nums[1] ^ nums[2] ^ nums[4] = 1 ^ 7 ^ 9 = 15 which has 4 set bits, an even number.
- (1, 3, 4) -> nums[1] ^ nums[3] ^ nums[4] = 1 ^ 3 ^ 9 = 11 which has 3 set bits, an odd number.
- (2, 3, 4) -> nums[2] ^ nums[3] ^ nums[4] = 7 ^ 3 ^ 9 = 5 which has 2 set bits, an even number.
So the answer is 4.

Constraints:

3 <= nums.length <= 1000
1 <= nums[i] <= 10⁸

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 possible value of each element in the input array?
Can the input array be empty or null?
Are duplicate numbers allowed within the input array?
If no such triplet exists, what should I return (e.g., 0, -1, null)?
By 'set bits', do you mean the number of bits that are '1' in the binary representation of the XOR result?

Brute Force Solution

Approach

The goal is to find groups of three numbers that satisfy a specific XOR property related to the number of set bits. The brute force method simply examines every possible combination of three numbers from the given set.

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

Pick the first number from the collection.
Then, pick a second number from the collection.
Next, pick a third number from the collection.
Combine these three numbers using a special operation called XOR.
Count how many '1's are in the result of the XOR operation.
If the count of '1's is an even number, then we've found a valid group of three numbers.
Keep a running total of how many valid groups we find.
Repeat this process, trying every possible combination of three numbers from the collection. Make sure to consider every number at least once.
Finally, report the total number of valid groups found.

Code Implementation

def count_triplets_with_even_xor_set_bits_i(numbers):
    count_of_valid_triplets = 0

    for first_index in range(len(numbers)): 
        for second_index in range(len(numbers)): 
            for third_index in range(len(numbers)): 

                # Calculate XOR of the three numbers
                xor_result = numbers[first_index] ^ numbers[second_index] ^ numbers[third_index]

                # Count set bits in the XOR result
                set_bits_count = 0
                temp_result = xor_result
                while temp_result > 0:
                    temp_result &= (temp_result - 1)
                    set_bits_count += 1

                # Check if the count of set bits is even
                # We increment if the condition is met
                if set_bits_count % 2 == 0:
                    count_of_valid_triplets += 1

    return count_of_valid_triplets

Big(O) Analysis

Time Complexity

O(n^3) – The brute force approach iterates through all possible triplets in the input array of size n. The outermost loop iterates n times. The second loop, nested inside the first, also iterates n times. A third loop, nested inside the second iterates n times. Inside the innermost loop, a constant amount of work (XOR and bit counting) is performed. Therefore, the time complexity is O(n*n*n), which simplifies to O(n^3).

Space Complexity

O(1) – The provided algorithm iterates through all possible triplets using nested loops. No auxiliary data structures like arrays, hash maps, or recursion are employed to store intermediate results. Only a few constant space variables are used to store the count of valid triplets and loop indices, independent of the input array's size (N). Therefore, the space complexity is constant.

Optimal Solution

Approach

The core idea is to leverage the properties of the XOR operation. The parity (evenness or oddness) of the set bits in a number after an XOR operation depends only on the parity of the set bits in the original numbers. Thus, we can optimize the counting process.

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

First, figure out whether each number in the set has an even or odd number of '1's in its binary representation.
Then, realize that for the XOR of three numbers to have an even number of '1's, either all three numbers must have an even number of '1's, or one number must have an even number of '1's and the other two must have an odd number of '1's.
Count how many numbers have an even number of '1's and how many have an odd number of '1's.
Use those counts to determine how many combinations of three numbers satisfy the condition above (all even, or one even and two odd).
The total number of such combinations is your answer.

Code Implementation

def count_triplets_with_even_xor_set_bits(numbers):
    even_parity_count = 0
    odd_parity_count = 0

    for number in numbers:
        set_bits_count = 0
        temp_number = number
        while temp_number > 0:
            set_bits_count += temp_number & 1
            temp_number >>= 1

        # Count even and odd parity numbers.
        if set_bits_count % 2 == 0:
            even_parity_count += 1
        else:
            odd_parity_count += 1

    # Calculate combinations: all even or one even and two odd.
    all_even_triplets = even_parity_count * (even_parity_count - 1) * (even_parity_count - 2) // 6

    # Count combinations of one even and two odd numbers
    one_even_two_odd_triplets = even_parity_count * odd_parity_count * (odd_parity_count - 1) // 2

    return all_even_triplets + one_even_two_odd_triplets

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array once to determine the parity of the number of set bits for each element. This first step has a time complexity of O(n), where n is the size of the input array. Calculating the number of combinations based on the counts of even and odd parity numbers involves constant time operations. Thus, the dominant factor is the initial iteration, making the overall time complexity O(n).

Space Complexity

O(1) – The solution only uses a few integer variables to store the counts of numbers with even and odd set bits. The number of such variables remains constant regardless of the input array's size (N). Thus, the auxiliary space used by the algorithm is constant, resulting in O(1) space complexity.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0, as there are no triplets possible.
Input array with fewer than 3 elements	Return 0, since a triplet cannot be formed.
Array with all elements being 0	The XOR of all elements will be 0, and its bit count will be even, so the number of triplets will be n * (n-1) * (n-2) / 6.
Array with all elements being 1	The XOR of any three 1's is 1, which has an odd number of set bits, so return 0.
Array with maximum possible integer values	Ensure that the XOR operation does not cause an integer overflow leading to incorrect bit counts.
Array with a mix of very large and very small numbers	The XOR operation and bit counting should work correctly irrespective of the magnitude differences.
Large input array (scalability concern)	Ensure the solution avoids nested loops and uses efficient data structures for optimal time complexity.
No triplet exists with an even number of set bits after XORing	The algorithm should correctly return 0 in this scenario.