Number of Unique XOR Triplets II
MedPrompt
You are given an integer array nums.
A XOR triplet is defined as the XOR of three elements nums[i] XOR nums[j] XOR nums[k] where i <= j <= k.
Return the number of unique XOR triplet values from all possible triplets (i, j, k).
Example 1:
Input: nums = [1,3]
Output: 2
Explanation:
The possible XOR triplet values are:
(0, 0, 0) → 1 XOR 1 XOR 1 = 1(0, 0, 1) → 1 XOR 1 XOR 3 = 3(0, 1, 1) → 1 XOR 3 XOR 3 = 1(1, 1, 1) → 3 XOR 3 XOR 3 = 3
The unique XOR values are {1, 3}. Thus, the output is 2.
Example 2:
Input: nums = [6,7,8,9]
Output: 4
Explanation:
The possible XOR triplet values are {6, 7, 8, 9}. Thus, the output is 4.
Constraints:
1 <= nums.length <= 15001 <= nums[i] <= 1500
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most straightforward approach. We iterate through all possible triplets of elements from the input array nums. For each triplet, we calculate the XOR sum and store it in a hash set to keep track of unique values. The final answer is the size of the hash set.
Algorithm
- Initialize a
HashSet<Integer>calleduniqueXorValuesto store the unique results. - Get the length of the array,
n = nums.length. - Use three nested loops to iterate through all combinations of indices
(i, j, k)where0 <= i < n,0 <= j < n, and0 <= k < n. - Inside the innermost loop, calculate
xorSum = nums[i] ^ nums[j] ^ nums[k]. - Add
xorSumto theuniqueXorValuesset. The set automatically handles duplicates. - After the loops complete, the number of unique XOR triplet values is the size of the set. Return
uniqueXorValues.size().
Walkthrough
The brute-force method systematically checks every possible triplet. Since the problem asks for triplets (i, j, k) with i <= j <= k, this implies choosing three elements from nums with replacement. A simpler way to generate the same set of unique XOR values is to iterate i, j, and k independently from 0 to n-1. This is because the XOR operation is commutative and associative, so the order of elements does not affect the final value (e.g., nums[i] ^ nums[j] ^ nums[k] is the same as nums[j] ^ nums[i] ^ nums[k]). A HashSet is used to efficiently store only the unique XOR sums encountered.
import java.util.HashSet;import java.util.Set; class Solution { public int countUniqueXorTriplets(int[] nums) { Set<Integer> uniqueXorValues = new HashSet<>(); int n = nums.length; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { uniqueXorValues.add(nums[i] ^ nums[j] ^ nums[k]); } } } return uniqueXorValues.size(); }}Complexity
Time
O(n^3), where `n` is the length of `nums`. We have three nested loops, each iterating `n` times.
Space
O(U), where `U` is the number of unique XOR triplet values. This is bounded by the maximum possible XOR value, which is less than 2048 given the problem constraints.
Trade-offs
Pros
Simple to understand and implement.
Cons
Very slow due to its cubic time complexity.
Will not pass the time limits for the given constraints (
n <= 1500).
This approach improves upon the brute-force method by breaking down the calculation. Instead of a three-level nested loop, we can first compute all possible XOR sums of pairs of elements (nums[i] ^ nums[j]) and store these unique pairwise XOR sums in a set. Then, we iterate through this set of pairwise sums and XOR each of them with every element nums[k] from the original array. This reduces the complexity from cubic to quadratic.
Algorithm
- Initialize a
HashSet<Integer>calledpairXorsto store unique XOR values of pairs. - Iterate through all pairs of elements
(nums[i], nums[j])from the input array using two nested loops. - For each pair, calculate
nums[i] ^ nums[j]and add the result topairXors. - Initialize another
HashSet<Integer>calledtripletXorsfor the final unique triplet XORs. - Iterate through each value
pinpairXors. - For each
p, iterate through all elementsnuminnums. - Calculate
p ^ numand add it totripletXors. - The final answer is the size of
tripletXors.
Walkthrough
The core idea is to use the associative property of XOR: a ^ b ^ c = (a ^ b) ^ c. By pre-calculating all possible values of a ^ b, we can reduce the number of operations.
First, we generate all unique values of nums[i] ^ nums[j] and store them in a set, pairXors. This takes O(n^2) time. The size of this set is bounded by the maximum possible XOR value of two numbers in nums (less than 2048).
Next, we iterate through each pre-calculated pairwise XOR sum p and XOR it with every number num in the original nums array. The results are stored in a final set, tripletXors, to count the unique values. This step takes O(|pairXors| * n) time.
import java.util.HashSet;import java.util.Set; class Solution { public int countUniqueXorTriplets(int[] nums) { Set<Integer> pairXors = new HashSet<>(); int n = nums.length; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { pairXors.add(nums[i] ^ nums[j]); } } Set<Integer> tripletXors = new HashSet<>(); for (int pXor : pairXors) { for (int num : nums) { tripletXors.add(pXor ^ num); } } return tripletXors.size(); }}Complexity
Time
O(n^2 + |P| * n), where `n` is the length of `nums` and `|P|` is the number of unique pairwise XOR sums. Since `|P|` is bounded by a constant related to the maximum value in `nums` (let's call it `V_max`), the complexity is effectively O(n^2 + V_max * n), which is dominated by O(n^2) for the given constraints.
Space
O(V_max), where `V_max` is the maximum possible XOR value (approx. 2048). This space is used for storing the `pairXors` and `tripletXors` sets.
Trade-offs
Pros
Significantly faster than the brute-force approach.
Efficient enough to pass the given constraints.
Cons
While much better than O(n^3), it might still be too slow if
nwere significantly larger.
This is the most advanced and efficient approach. The problem of finding all possible values of a ^ b ^ c can be modeled as a threefold XOR convolution of a set with itself. The Fast Walsh-Hadamard Transform (FWHT) is an algorithm that can compute XOR convolution in O(N log N) time, which is significantly faster than the naive O(N^2) method.
Algorithm
- Determine the size
Vfor our arrays. It must be a power of 2 large enough to hold any possible XOR sum. Givenmax(nums[i]) <= 1500,V = 2048is sufficient. - Create a frequency array
Pof sizeV(usinglongto prevent overflow). For eachnuminnums, setP[num] = 1. - Apply the Fast Walsh-Hadamard Transform (FWHT) to
P. Let's call the resulthat_P. - Create a new array
hat_P3by cubing each element ofhat_P:hat_P3[i] = hat_P[i] * hat_P[i] * hat_P[i]. This corresponds to the transform of the threefold convolution. - Apply the inverse FWHT to
hat_P3to get the result arrayP3. The valueP3[k]will represent the number of ways the valuekcan be formed by XORing three numbers fromnums. - Count the number of indices
kfor whichP3[k]is non-zero. This count is the number of unique XOR triplet values.
Walkthrough
We can represent the set of numbers in nums as a frequency array A, where A[i] is 1 if i is present in nums, and 0 otherwise. Finding all possible values of a ^ b ^ c is equivalent to finding the support (the set of indices with non-zero values) of the threefold XOR convolution A * A * A.
The FWHT provides a powerful tool for this. Based on the convolution theorem, FWHT(A * B) = FWHT(A) .* FWHT(B) (where .* denotes element-wise product). We can leverage this to compute the convolution efficiently.
The process involves transforming the frequency array A into the FWHT domain, performing element-wise cubing (for the threefold convolution), and then transforming it back with the inverse FWHT. The final array's non-zero entries give us the unique XOR triplet values.
class Solution { public int countUniqueXorTriplets(int[] nums) { // V must be a power of 2 and >= max possible XOR sum. // Max value is 1500, so max XOR sum of 3 numbers is < 2048. int V = 2048; long[] p = new long[V]; for (int num : nums) { p[num] = 1; } // Forward FWHT fwht(p, false); // Element-wise cube in the transform domain for (int i = 0; i < V; i++) { p[i] = p[i] * p[i] * p[i]; } // Inverse FWHT fwht(p, true); int count = 0; for (int i = 0; i < V; i++) { if (p[i] > 0) { count++; } } return count; } // In-place Fast Walsh-Hadamard Transform for XOR convolution private void fwht(long[] a, boolean inverse) { int n = a.length; for (int len = 1; len < n; len <<= 1) { for (int i = 0; i < n; i += 2 * len) { for (int j = 0; j < len; j++) { long u = a[i + j]; long v = a[i + len + j]; a[i + j] = u + v; a[i + len + j] = u - v; } } } if (inverse) { for (int i = 0; i < n; i++) { a[i] = a[i] / n; } } }}Complexity
Time
O(V log V), where `V` is the power of 2 that bounds the maximum possible XOR value. Given the constraints, `V=2048`, so the complexity is very low and constant with respect to `n`.
Space
O(V), where `V` is the power of 2 that bounds the maximum possible XOR value (2048 in this case). This space is for the frequency/transform array.
Trade-offs
Pros
Extremely efficient, with a quasi-linear time complexity.
It is the asymptotically fastest known method for this type of problem.
Cons
The concept of FWHT is more complex and less intuitive than other approaches.
Implementation requires careful handling of details like data types (using
longto avoid overflow) and the transform logic.
Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.