Skip to main content
Talentd

Number of Unique XOR Triplets I - Solution & Explanation

MediumArrayMathBit Manipulation8 min readAsked at: Meesho
Practice this problem

Problem Statement

You are given an integer array nums of length n, where nums is a permutation of the numbers in the range [1, n].

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,2]

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 2 = 2
  • (0, 1, 1) → 1 XOR 2 XOR 2 = 1
  • (1, 1, 1) → 2 XOR 2 XOR 2 = 2

The unique XOR values are {1, 2}, so the output is 2.

Example 2:

Input: nums = [3,1,2]

Output: 4

Explanation:

The possible XOR triplet values include:

  • (0, 0, 0) → 3 XOR 3 XOR 3 = 3
  • (0, 0, 1) → 3 XOR 3 XOR 1 = 1
  • (0, 0, 2) → 3 XOR 3 XOR 2 = 2
  • (0, 1, 2) → 3 XOR 1 XOR 2 = 0

The unique XOR values are {0, 1, 2, 3}, so the output is 4.

 

Constraints:

  • 1 <= n == nums.length <= 105
  • 1 <= nums[i] <= n
  • nums is a permutation of integers from 1 to n.

Approach Overview

Problem Overview: You receive an integer array and must compute how many distinct values can be produced by XORing three different elements nums[i] ^ nums[j] ^ nums[k] with i < j < k. The challenge is not generating the triplets, but ensuring the XOR results are counted uniquely.

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

Iterate through every possible triplet using three nested loops. For each combination (i, j, k), compute nums[i] ^ nums[j] ^ nums[k] and store the result in a hash set. The set automatically removes duplicates, leaving only unique XOR values. This approach is easy to reason about and works for very small arrays, but the cubic iteration quickly becomes impractical as n grows.

Approach 2: Pair XOR + Third Element (O(n^2) time, O(U) space)

XOR has a useful associative property: a ^ b ^ c = (a ^ b) ^ c. Instead of building triplets directly, first compute XOR values for pairs. While scanning the array, maintain a collection of pair XORs from earlier indices. For the current element nums[k], combine it with each stored pair XOR and insert the result into a result set. Because each pair represents (i, j) with i < j < k, the index constraint holds automatically. This reduces the search space from three nested loops to two.

If the integer range is limited (common in XOR problems), the result space is also bounded. You can replace hash sets with a boolean array indexed by XOR value, reducing constant factors. The algorithm still iterates over roughly n^2 pair combinations but avoids redundant triplet enumeration.

The technique relies on properties from bit manipulation, especially XOR associativity. The iteration logic is straightforward using standard array traversal, while the uniqueness constraint is handled through set membership or a fixed boolean lookup. Some implementations also reason about the limited XOR value range using simple math observations.

Recommended for interviews: The pair-XOR approach. Start by mentioning the brute force to demonstrate baseline understanding. Then reduce the complexity by grouping two numbers first and combining them with the third using XOR associativity. Interviewers expect you to recognize that (a ^ b) ^ c allows collapsing a triple loop into pair preprocessing, bringing the runtime down to O(n^2).

Solution

Since nums is a permutation of [1, n], the available values are fixed as {1, 2, ldots, n}. With indices satisfying i \le j \le k, the same index may be chosen more than once, so a XOR triplet is equivalent to picking three numbers (with replacement) from this set and taking their XOR.

When n \le 2, enumeration shows the answers are 1 (n = 1) and 2 (n = 2), i.e., the answer equals n.

When n \ge 3, it can be shown that all possible XOR results exactly fill the interval [0, 2^{k} - 1], where 2^{k} is the smallest power of 2 strictly greater than n. This value also equals 2^{\lfloor log_2 n \rfloor + 1}, which can be obtained via each language's bit-length function:

$ ans = 1 \ll bitLength(n)

For example, when n = 3, bitLength(3) = 2, so the answer is 4, matching the example set {0, 1, 2, 3}.

The time complexity is O(1), and the space complexity is O(1)$.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force TripletsO(n^3)O(U)Useful for understanding the problem or when the array size is very small
Pair XOR + Third ElementO(n^2)O(U)General optimal solution using XOR associativity and pair preprocessing
Pair XOR with Boolean LookupO(n^2)O(K)When XOR values are bounded (e.g., ≤1024), allowing faster constant-time checks

Video Solution

Leetcode 3513 | Number of unique XOR triplets I | Leetcode biweekly contest 154 | Beginner friendly • CodeWithMeGuys • 1,010 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Number of Unique XOR Triplets I easy or hard?
The problem is rated Medium because the brute force idea is straightforward, but recognizing the XOR associativity trick to reduce complexity requires familiarity with bit manipulation patterns.
Number of Unique XOR Triplets I Python/Java solution
Typical implementations iterate through the array while maintaining pair XOR values and inserting final XOR results into a set. The same O(n^2) logic works across Python, Java, C++, and Go since it only relies on nested iteration and constant-time set lookups.
How to solve Number of Unique XOR Triplets I in O(n^2)?
Compute XOR values for pairs while scanning the array. For each element k, combine nums[k] with previously computed pair XOR values and insert the results into a set of unique XOR outputs. Because XOR is associative, (a ^ b) ^ c covers all triplet combinations while avoiding triple nested loops.
What is the best approach for Number of Unique XOR Triplets I?
The most practical solution uses XOR associativity: compute XOR for pairs first, then combine each pair result with a third element. This reduces the complexity from O(n^3) brute force to O(n^2). A set or boolean array tracks distinct XOR outcomes.
Is Number of Unique XOR Triplets I asked at Google/Amazon/Meta?
Problems involving XOR combinations and unique results appear frequently in interviews at companies like Google, Amazon, and Meta. They test understanding of bit manipulation, hash sets, and recognizing algebraic properties like XOR associativity to reduce complexity.
What data structure is used in Number of Unique XOR Triplets I?
Most solutions rely on a hash set to store distinct XOR results. Some implementations use a boolean array if the XOR range is small, which provides constant-time membership checks and lower overhead than a hash set.
What is the time complexity of Number of Unique XOR Triplets I?
The brute force method runs in O(n^3) time by checking every triplet. An optimized solution groups two numbers first and combines them with the third, reducing the complexity to O(n^2) with O(U) space for storing unique XOR values.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays