Is Number of Unique XOR Triplets II easy or hard?

The problem is typically classified as Medium because the brute force solution is obvious but inefficient. Recognizing XOR associativity and restructuring the loops to avoid O(n^3) enumeration is the key step that raises the difficulty.

Number of Unique XOR Triplets II Python/Java solution

Most implementations iterate through pairs, compute pair XOR values, and combine them with a third element while inserting results into a set. The logic is identical across Python, Java, C++, and Go; only the set syntax and iteration style differ. Time complexity remains around O(n^2).

How to solve Number of Unique XOR Triplets II in O(n^2)?

Compute XOR values for all element pairs and reuse them when forming triplets. Since XOR is associative, a pair XOR combined with a third element gives the same result as computing the triplet directly. Store resulting values in a hash set to keep only distinct XOR outcomes, resulting in about O(n^2) time.

What is the best approach for Number of Unique XOR Triplets II?

The practical approach enumerates XOR values for pairs and then combines them with a third element. Because XOR is associative, (a ^ b) ^ c equals a ^ b ^ c, allowing you to reuse pair results. This reduces the complexity from O(n^3) brute force to roughly O(n^2) with a hash set used to track unique results.

Is Number of Unique XOR Triplets II asked at Google/Amazon/Meta?

XOR enumeration and bit‑manipulation problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of triplet XOR counting test whether candidates recognize XOR properties and reduce brute force enumeration.

What data structure is used in Number of Unique XOR Triplets II?

Hash sets are the primary data structure. They store XOR values from triplets (or intermediate pair XORs) and automatically remove duplicates. Arrays provide the input traversal, while the optimization relies on bit manipulation operations during XOR computation.

What is the time complexity of Number of Unique XOR Triplets II?

The brute force solution checks every triplet and runs in O(n^3) time. An optimized method computes pair XOR values and combines them with another element, bringing the runtime down to about O(n^2). Space complexity typically ranges from O(k) to O(n^2) depending on how pair results are stored.

Description Hints 5 Solution Video 3:35

3514. Number of Unique XOR Triplets II

Medium52.9% acceptance1 company

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

Asked at 1 company

Meesho

Topics

Hints open one at a time

Hint 1

What is the maximum possible XOR value achievable by any triplet?

Hint 2

Let the maximum possible XOR value be stored in max_xor.

Hint 3

For each index i, consider all pairs of indices (j, k) such that i <= j <= k. For each such pair, compute the triplet XOR as nums[i] XOR nums[j] XOR nums[k].

Hint 4

You can optimize the calculation by precomputing or reusing intermediate XOR results. For example, after fixing an index i, compute XORs of pairs (j, k) in O(n²) time instead of checking all three indices independently.

Hint 5

Finally, count the number of unique XOR values obtained from all triplets.

3:35

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def uniqueXorTriplets(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,3]

Input

[6,7,8,9]

Your code is saved on this device.Solution