Scale Engineer

Number of Unique XOR Triplets II

Med
#3126Time: 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.
Patterns
MathBit ManipulationEnumeration
Data structures
Array

Prompt

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 <= 1500
  • 1 <= 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> called uniqueXorValues to 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) where 0 <= i < n, 0 <= j < n, and 0 <= k < n.
  • Inside the innermost loop, calculate xorSum = nums[i] ^ nums[j] ^ nums[k].
  • Add xorSum to the uniqueXorValues set. 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).

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.

← Previous

Previous problem

Next →

Next problem