Number of Unique XOR Triplets II - Solution & Explanation

Q: 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.

Q: 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).

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

MediumArray Math Bit Manipulation Enumeration9 min readAsked at: Meesho

Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given an array and must compute how many distinct XOR values can be formed using triplets of indices. Each triplet contributes a ^ b ^ c. The goal is not the number of triplets but the number of unique XOR results they produce.

Approach 1: Brute Force Triplet Enumeration (O(n^3) time, O(k) space)

The most direct solution iterates over every possible triplet (i, j, k) with three nested loops. For each combination, compute nums[i] ^ nums[j] ^ nums[k] and store the result in a hash set to keep only distinct values. After processing all triplets, the size of the set gives the answer. This approach is easy to reason about and confirms correctness, but the O(n^3) runtime becomes impractical once the array grows beyond a few hundred elements.

Approach 2: Pair XOR Enumeration with Set Deduplication (O(n^2) time, O(n^2) space)

A more efficient strategy reduces one level of enumeration. First compute XOR values for all index pairs and store them in a structure such as a set or list. Then combine each pair XOR with every element to produce candidate triplet XOR values. Because (a ^ b) ^ c = a ^ b ^ c, this transformation preserves the result while avoiding the explicit third nested loop over indices. Store the generated values in a set to ensure uniqueness. The algorithm performs roughly O(n^2) pair computations and another O(n^2) combinations, which is far more manageable than cubic enumeration.

The key insight is the associativity of XOR. Grouping two numbers first lets you reuse pair results across multiple triplets. Hash sets handle deduplication efficiently, making the solution practical for medium-sized arrays.

Conceptually this problem sits at the intersection of array processing, bit manipulation, and some light mathematical reasoning. Recognizing XOR properties—associativity, commutativity, and self-cancellation—is what enables the optimization.

Recommended for interviews: Start with the brute force explanation to demonstrate understanding of the problem space. Then move to the pair‑XOR enumeration approach. Interviewers expect candidates to notice that XOR can be regrouped, allowing a reduction from O(n^3) to about O(n^2) while still using simple data structures like sets.

Solution

With indices satisfying i \le j \le k, the same index may be chosen more than once, and XOR is commutative. Therefore, the answer equals the number of distinct XOR values obtainable by picking any three elements from the array (with replacement).

Let M = max(nums). The XOR of any two non-negative integers at most M is less than 2M, so a boolean array of length 2M can be used for marking.

First enumerate all pairs (a, b) and mark a \oplus b in array st. Then enumerate every appeared pairwise XOR value ab and each third element c, and mark ab \oplus c in array s. Finally count the number of non-zero entries in s.

The time complexity is O(n^2 + M cdot n), and the space complexity is O(M), where n is the length of the array and M is the maximum value in the array.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Brute Force Triplet Enumeration	O(n^3)	O(k) for unique XOR set	Small arrays or when validating correctness during implementation
Pair XOR Enumeration + Hash Set	O(n^2)	O(n^2)	General case; significantly faster by leveraging XOR associativity
Pair XOR with On‑the‑fly Deduplication	O(n^2)	O(k)	When memory is tighter and pair results are combined immediately

Video Solution

Leetcode | biweekly-contest-154 | Number of Unique XOR Triplets II • CodeWithMe21 • 494 views views

Watch 2 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Number of Unique XOR Triplets II with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyMedium

Acceptance52.9%

Approaches1

Reading time9 min

Asked at

Meesho