Number of Unique XOR Triplets I — LeetCode Daily Python Solution (the trick nobody sees)

Introduction

Every so often a LeetCode problem looks like a brute-force exercise and turns out to be a math problem in disguise. Number of Unique XOR Triplets I is exactly that kind of problem, and it's worth your time for a reason that has nothing to do with LeetCode streaks: the pattern it teaches — counting the size of a result space instead of generating every result — shows up constantly in real systems. Hash collision counts, checksum coverage, error-correcting code capacity, and even cache key distributions all boil down to the same question: "how many distinct outputs can this operation produce?"

Interviewers like this problem because it has a trap built in. The naive triple-loop solution is easy to write and passes on small inputs, which makes candidates confident they're done. Then the constraint reveals that n can be up to 100,000, and a solution that felt correct suddenly can't finish in time. Watching how a candidate reacts to that — do they re-examine their assumptions, or just try to optimize the same loop? — tells an interviewer a lot.

By the end of this article you'll understand why the actual numbers in the array are irrelevant, why XOR combinations of a permutation fill every value up to a power of two, and how to turn that insight into a five-line, constant-time Python solution.

Problem Overview

You're given an array nums that is a permutation of the integers 1 to n — meaning it contains every value from 1 through n exactly once, just shuffled into some order.

You need to consider every triplet of indices (i, j, k) such that i <= j <= k. Because indices are allowed to repeat (you can pick the same index for i, j, and k), this is not the same as choosing three distinct array positions — it includes triplets like i = j = k.

For each such triplet, compute nums[i] XOR nums[j] XOR nums[k]. Collect every distinct value this expression can produce, and return the count of distinct values.

The tricky part isn't the XOR itself — it's recognizing that the array being a permutation makes the positions irrelevant, and the real question is about the values 1 through n.

Example

Let's use nums = [1, 2] (so n = 2).

Valid index triplets with i <= j <= k:

• (0,0,0) → nums[0] XOR nums[0] XOR nums[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 distinct results are {1, 2} — so the answer is 2.

Now try n = 4. Instead of enumerating every triplet by hand (there are 4×4×4 = 64 index combinations, though many index combinations produce the same value-triplet), trust the pattern for a moment: the distinct XOR results turn out to be every integer from 0 to 7 — all eight values. We'll prove why shortly.

Intuition

Start with the single fact that makes this entire problem tractable:

a XOR a = 0 — XOR-ing a number with itself cancels it out, like flipping a light switch on and then off.

This is the mechanism behind almost every XOR trick you'll ever see in an interview, from "find the single number" to "find the missing number" to this problem.

Step 1 — the positions don't matter. Since nums is a permutation, choosing indices i <= j <= k with repetition allowed is really just choosing a multiset of three values from {1, ..., n}, with repetition allowed. XOR is commutative (a XOR b = b XOR a) and repetition-aware (a XOR a = 0), so the order you combine values in doesn't change the result. The array's actual arrangement is a red herring — only n matters.

Step 2 — the values fill an entire range. This is the part that feels like magic the first time you see it. Take the smallest power of two that is strictly greater than n — call it C (the "ceiling"). It turns out that once n >= 3, combining three values from 1 to n with XOR can produce every single integer from 0 to C - 1.

Why? Every bit position below bit_length(n) is "reachable" — because the numbers 1 through n collectively contain a number that has just that one bit set at the top, and combinations of a few such numbers with XOR let you build up any target bit pattern below that ceiling. With three numbers to combine (repetition allowed), you have enough freedom to reach every value in that range. This is really a fact from linear algebra over GF(2) — the integers 1..n, viewed as bit vectors, span the entire space below bit_length(n) bits, and three "slots" (with repeats allowed, so you can effectively use fewer than three distinct numbers) is enough freedom to reach any element of that span.

Check it: n = 4. bit_length(4) is 3 (binary 100), so C = 1 << 3 = 8. Every value 0 through 7 is reachable. No triplet needs to be tried — the ceiling alone tells you the count.

The two exceptions. With only one number (n = 1), there's exactly one possible triplet, giving one result. With two numbers (n = 2), there isn't enough freedom to fill the full bit range — working it out by hand always gives exactly 2 distinct results, not C. Both cases are handled directly rather than forced through the formula.

Brute Force Solution

Idea: Loop over every (i, j, k) with i <= j <= k, XOR the three values, and drop the result into a set.

Algorithm:

1. Create an empty set.
2. For each i from 0 to n-1, each j from i to n-1, each k from j to n-1: compute nums[i] ^ nums[j] ^ nums[k] and add it to the set.
3. Return the size of the set.

Advantages: Obviously correct, trivial to write, easy to reason about.

Disadvantages: Far too slow for the actual constraint (n up to 100,000). It also does unnecessary work — it never notices that only n matters, not the array's contents.

Complexity: Time O(n³) (or O(n²) with a pairwise-XOR precomputation trick), Space O(n²) in the worst case for the intermediate set of pairs, or O(distinct results) for the final set.

Optimal Solution

Once you accept the two insights from the intuition section, the algorithm collapses to almost nothing:

n	Special case?	Answer
1	yes	1
2	yes	2
≥ 3	no	1 << n.bit_length()

Here, n.bit_length() returns the number of bits needed to represent n in binary, and 1 << k computes 2^k. Together, 1 << n.bit_length() gives you the smallest power of two strictly greater than n — exactly the "ceiling" from the intuition.

No loop over the array is needed at all, because the array's contents never mattered — only its length.

Python Code

def unique_xor_triplets(n: int) -> int:
    """
    Count distinct XOR results of nums[i] ^ nums[j] ^ nums[k]
    for i <= j <= k, where nums is a permutation of 1..n.
    """
    if n == 1:
        return 1
    if n == 2:
        return 2
    return 1 << n.bit_length()


# Self-checks
assert unique_xor_triplets(1) == 1
assert unique_xor_triplets(2) == 2
assert unique_xor_triplets(4) == 8
assert unique_xor_triplets(5) == 8

Code Walkthrough

• if n == 1: return 1 — with a single element, i = j = k = 0 is the only triplet, so there's exactly one possible result.
• if n == 2: return 2 — too few values for the full bit-ceiling range to be reachable; verified directly by enumeration, so it's hardcoded.
• 1 << n.bit_length() — for n >= 3, this is the closed-form answer. n.bit_length() gives the number of bits in n; shifting 1 left by that many places gives the next power of two above n.
• No loop touches nums at all — the function only needs the count of elements, not their values.

Dry Run

Take n = 5.

1. n != 1 and n != 2, so we fall through to the formula.
2. 5 in binary is 101, which uses 3 bits, so n.bit_length() == 3.
3. 1 << 3 == 8.
4. Return 8.

Sanity check: for n = 5, the set {1, 2, 3, 4, 5} should be able to XOR-combine (in triplets, repetition allowed) into every value from 0 to 7. n = 6 and n = 7 also map to 8, since the ceiling only changes when n crosses a power of two — the function is a step function.

Complexity Analysis

Time: O(1). bit_length() and a bit shift are constant-time operations on Python's arbitrary-precision integers (in practice, proportional to the number of bits in n, which is at most ~17 for n <= 100,000 — effectively constant).

Space: O(1). No auxiliary data structures are allocated.

This is correct because the array is never read beyond its length — the entire problem reduces to a fact about the set {1, ..., n}, which is fixed and doesn't depend on the array's arrangement.

Alternative Solutions

The only reasonable alternative is the O(n²) refinement of brute force: precompute all pairwise XORs of array elements into a set, then XOR each pair-result with every single element and collect the results. This shaves a factor of n off the naive triple loop but is still far too slow at n = 100,000 (roughly 10 billion operations). It's worth knowing as a fallback if you can't see the permutation trick under interview pressure, but it isn't a substitute for the closed-form answer.

Edge Cases

• n = 1 — only one triplet exists; handled explicitly, returns 1.
• n = 2 — too small for the bit-ceiling pattern; handled explicitly, returns 2.
• n exactly a power of two (e.g., n = 8) — bit_length(8) = 4, so the ceiling is 16, not 8. Double-check this boundary; it's the easiest place to introduce an off-by-one.
• Large n (100,000) — the solution is O(1), so this is a non-issue, unlike brute force.
• Duplicate values — not applicable, since the array is guaranteed to be a permutation of 1..n with no duplicates.

Common Mistakes

1. Looping over the array at all. If your solution reads nums, you've missed the core insight — the values never matter, only len(nums).
2. Forgetting the n = 1 and n = 2 special cases and applying the bit-ceiling formula uniformly, which gives wrong answers for those two inputs.
3. Off-by-one on the ceiling. Using 1 << (n.bit_length() - 1) (the largest power of two at most n) instead of 1 << n.bit_length() (the smallest power of two above n).
4. Assuming index order matters. Spending time tracing through i, j, k positions in the array instead of recognizing that a permutation collapses index selection into value selection.
5. Reaching for a nested loop by default instead of first asking "does the problem's structure (permutation, fixed range) let me count outputs without generating them?"

Interview Questions

• "What if nums were not guaranteed to be a permutation of 1..n?" — You'd fall back to building a linear XOR basis via Gaussian elimination over the array's values; the answer becomes 2^rank of that basis.
• "Why does the closed-form only kick in at n >= 3?" — Because three "slots" with repetition are the minimum degrees of freedom needed to span the full bit range implied by bit_length(n).
• "What's the total number of index triplets, ignoring duplicates?" — n³, since each of i, j, k independently ranges over all n positions (before applying i <= j <= k).
• "Can you prove the ceiling bound instead of just asserting it?" — This invites the GF(2) vector-space argument: the integers 1..n span every bit position below bit_length(n).

Similar Problems

• Single Number (LeetCode 136) — same a XOR a = 0 cancellation idea, applied to find a unique element.
• Missing Number (LeetCode 268) — uses XOR over a range to find a missing value, another "range property" trick.
• Maximum XOR of Two Numbers in an Array (LeetCode 421) — uses a XOR trie/basis, relevant if nums isn't a clean permutation.
• Counting Bits (LeetCode 338) — different mechanism, same theme of exploiting a numeric range's structure instead of brute force.

Key Takeaways

• When a problem gives you a permutation of 1..n, check whether index constraints secretly reduce to value constraints.
• a XOR a = 0 is the single fact behind most XOR interview problems — internalize it.
• "Count distinct results" problems often hide a closed-form size of the output space; look for that before writing a loop.
• n.bit_length() and 1 << k are the Python tools for reasoning about powers of two and bit ranges — know them cold.

Watch the Video

If you want to see this bit-ceiling shortcut built up visually, step by step, with the light-switch analogy and a worked walkthrough for n = 5, watch the full video here: {LINK}

About the Series

This breakdown is part of the Daily Python LeetCode series, where each entry takes the current LeetCode daily challenge and rebuilds it from first principles in Python — starting from the obvious brute force, then working toward the insight that actually makes the problem fast. The goal isn't just to pass the test cases; it's to build the pattern-recognition instincts that make future problems easier to see through.

Call To Action

If this shortcut clicked for you, the video walks through the same reasoning with visuals that make the bit-ceiling idea even more intuitive — give it a watch and a like on YouTube. Subscribe there for daily problem breakdowns, and subscribe to the Substack newsletter for written deep-dives like this one delivered straight to your inbox. Drop a comment with the next problem you'd like broken down, and share this with a study partner who's grinding LeetCode for interviews.

---

def numberOfUniqueXorTriplets(nums):
    n = len(nums)
    if n == 1:
        return 1
    if n == 2:
        return 2
    return 1 << n.bit_length()

assert numberOfUniqueXorTriplets([1, 2]) == 2
assert numberOfUniqueXorTriplets([3, 1, 2]) == 4