Count Triplets with Even XOR Set Bits II
Medium
4 views
Topics:
Bit Manipulation
You are given a 0-indexed array nums of positive integers.
You need to choose three distinct indices i, j, and k such that the number of set bits (i.e., the number of ones in the binary representation) in nums[i] XOR nums[j] XOR nums[k] is even.
Return the number of ways to choose such three indices.
Example 1:
Input: nums = [2,1,3,0] Output: 4 Explanation: The following are the possible choices of i, j, and k: - (i,j,k) = (0,1,2). nums[i] XOR nums[j] XOR nums[k] = 2 XOR 1 XOR 3 = 0. The number of set bits in 0 is 0, which is even. - (i,j,k) = (0,1,3). nums[i] XOR nums[j] XOR nums[k] = 2 XOR 1 XOR 0 = 3. The number of set bits in 3 is 2, which is even. - (i,j,k) = (0,2,3). nums[i] XOR nums[j] XOR nums[k] = 2 XOR 3 XOR 0 = 1. The number of set bits in 1 is 1, which is odd. - (i,j,k) = (1,2,3). nums[i] XOR nums[j] XOR nums[k] = 1 XOR 3 XOR 0 = 2. The number of set bits in 2 is 1, which is odd. Thus, the number of ways is 2. Note that (i,j,k) = (0,3,1) is not a valid choice because it is not in increasing order.
Example 2:
Input: nums = [1,2,3] Output: 0 Explanation: The following are the possible choices of i, j, and k: - (i,j,k) = (0,1,2). nums[i] XOR nums[j] XOR nums[k] = 1 XOR 2 XOR 3 = 0. The number of set bits in 0 is 0, which is even. Thus, the number of ways is 1.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 108
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 input array?
- What is the range of values within the input array? Can the numbers be negative or zero?
- Are there any constraints on the output, such as needing to avoid integer overflow given large input arrays?
- Are duplicate values allowed in the input array, and if so, how should they be handled in the triplet count?
- Could you define more precisely what constitutes 'set bits' for this problem? Are you referring to the number of bits that are '1' in the binary representation of the XOR result?
Brute Force Solution
Approach
The brute force method explores all possible combinations of three numbers from the given set. For each combination, we check if it meets our specific criteria. Finally, we count all combinations which passed the check.
Here's how the algorithm would work step-by-step:
- Pick the first number.
- Pick the second number from the remaining numbers.
- Pick the third number from the remaining numbers after picking the first and second.
- Combine these three numbers and perform a special calculation (XOR) on them.
- Count how many '1's are in the result of that calculation.
- If that count is an even number, then we found a valid combination of three numbers.
- Keep a running total of how many valid combinations we find.
- Repeat this process by trying all possible combinations of three numbers.
- After checking every single combination of three numbers, the running total is the answer.
Code Implementation
def count_triplets_with_even_xor_set_bits_brute_force(numbers):
numbers_length = len(numbers)
triplets_count = 0
for first_index in range(numbers_length):
for second_index in range(first_index + 1, numbers_length):
for third_index in range(second_index + 1, numbers_length):
# Calculate XOR of the three numbers
xor_result = numbers[first_index] ^ numbers[second_index] ^ numbers[third_index]
set_bits_count = 0
temp_xor_result = xor_result
# Count the set bits in the XOR result
while temp_xor_result > 0:
temp_xor_result &= (temp_xor_result - 1)
set_bits_count += 1
# Check if the number of set bits is even
if set_bits_count % 2 == 0:
# Increment the triplets count if even
triplets_count += 1
return triplets_countBig(O) Analysis
Time Complexity
O(n^3) – The provided solution iterates through all possible triplets in the input array of size n. The outer loop picks the first element, the second loop picks the second element after the first, and the third loop picks the third element after the first and second. This results in a nested loop structure where, for each element, we iterate over a shrinking subset of the array, leading to a computation that is proportional to n * (n-1) * (n-2). This approximates to n^3/6 operations, which simplifies to O(n^3).
Space Complexity
O(1) – The provided brute force method doesn't utilize any auxiliary data structures beyond a few counter variables. It iterates through combinations of three numbers in place without creating any temporary lists, hash maps, or recursion stacks. The space required for these counters remains constant, irrespective of the input size N (the number of elements). Therefore, the space complexity is constant.
Optimal Solution
Approach
The goal is to efficiently count specific groups of three numbers. The key is to recognize that for the condition to be met, there's a direct relationship between the number of set bits in the numbers, allowing us to derive one number from the others.
Here's how the algorithm would work step-by-step:
- First, focus on the fact that we need an even number of '1' bits in the result of combining the three numbers with 'exclusive or'. This means the total count of '1' bits in the three numbers must be even.
- Instead of checking all possible combinations of three numbers, we can pick any two numbers and then figure out the third number needed to satisfy the even bit count condition.
- For any two numbers we pick, we calculate the XOR of them. To achieve an even number of total set bits across all three, the third number must have the same number of set bits (parity) as the XOR result we just calculated.
- Count how many numbers in the original list have the required number of '1' bits needed to fulfill the triplet condition. This count directly tells us how many valid triplets can be formed using the initial two chosen numbers.
- Repeat this process for every possible pair of numbers from the original list. Accumulate the counts found at each step. This total count is your final answer.
- To make this faster, precalculate and store the number of set bits (population count) for all numbers in your original list to avoid redundant computations.
Code Implementation
def count_triplets(numbers):
number_of_elements = len(numbers)
count = 0
set_bit_counts = [bin(number).count('1') for number in numbers]
for first_index in range(number_of_elements):
for second_index in range(first_index + 1, number_of_elements):
# Calculate XOR of the two numbers.
xor_result = numbers[first_index] ^ numbers[second_index]
# We need to find the parity of the XOR result.
xor_set_bits = bin(xor_result).count('1')
valid_third_numbers = 0
# Count numbers with matching parity.
for third_index in range(number_of_elements):
if third_index != first_index and third_index != second_index:
if set_bit_counts[third_index] % 2 == xor_set_bits % 2:
valid_third_numbers += 1
# Accumulate triplets found.
count += valid_third_numbers
# Each triplet was counted 6 times so adjust result
return count // 3Big(O) Analysis
Time Complexity
O(n²) – The algorithm iterates through all possible pairs of numbers in the input array of size n. For each pair, it calculates the XOR and counts the number of elements with the same parity of set bits. The number of pairs considered is proportional to n * (n-1) / 2, which represents all combinations of two elements from n. Consequently, the time complexity is dominated by the nested loop structure that generates these pairs, resulting in approximately n²/2 operations. Therefore, the overall time complexity simplifies to O(n²).
Space Complexity
O(N) – The auxiliary space is dominated by the precalculation and storage of the number of set bits for each number in the original list. This requires an array (or similar data structure) of size N, where N is the number of elements in the input list. While other variables are used, their space is constant. Therefore, the overall auxiliary space complexity is O(N).
Edge Cases
| Case | How to Handle |
|---|---|
| Empty input array | Return 0 as no triplets can be formed. |
| Array with fewer than 3 elements | Return 0 as a triplet requires at least 3 elements. |
| Array with all elements being 0 | The XOR sum will always be 0, so the number of triplets is n choose 3, which can be calculated directly. |
| Array with all elements having an even number of set bits | The XOR sum of any combination will always have an even number of set bits; calculate n choose 3. |
| Array with all elements having an odd number of set bits | The XOR sum of any combination will always have an odd number of set bits; return 0. |
| Array with MAX_INT values which cause integer overflow in the XOR calculation | Use 64-bit integers (long) or bitset to prevent overflow during the XOR operation. |
| Input array with maximum size allowed | Ensure algorithm time complexity is better than O(n^3) to avoid time limit exceeded. |
| Array containing negative numbers (if applicable based on constraints) | Handle negative numbers in set bit counting if the problem explicitly allows it. |
Explore Interview QuestionsGoogle Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Jobs By LevelEntry-Level Software Engineer JobsMid-Level Software Engineer JobsSenior Software Engineer JobsStaff Software Engineer Jobs
