3513. Number of Unique XOR Triplets I

Problem Overview

nums is always a permutation of 1..n, so only n matters.

Intuition

nums is always a permutation of 1..n, so only n matters. With i ≤ j ≤ k you may reuse the same index, which makes small cases trivial (n=1 → {1}, n=2 → {1,2}). Once n ≥ 3, XOR of three values from 1..n can produce every integer in a full bit window [0, 2^b − 1], where 2^b is the smallest power of two strictly above the highest bit of n — i.e. answer = 1 << (⌊log2 n⌋ + 1).

Algorithm

1Let n = nums.Length.
2If n ≤ 2, return n.
3Otherwise compute b = floor(log2(n)) + 1 and return 1 << b.

Example Walkthrough

Input: nums = [1, 2, 3, 4] (n = 4)

1.n ≥ 3, so use the closed form.
2.⌊log2(4)⌋ + 1 = 2 + 1 = 3.
3.Answer = 1 << 3 = 8, covering distinct XOR values 0..7.

Output: 8

Common Pitfalls

•Handle n = 1 and n = 2 separately — the power-of-two formula overcounts for those.
•Do not iterate all triplets; n up to 1e5 makes O(n³) impossible.
•The array values themselves are irrelevant beyond being a permutation of 1..n — only length matters.
•⌊log2(n)⌋ + 1 is the bit-width of n; 1 << that equals the next power of two when n is not already a power of two, and twice n when it is.

3513.cs

public class Solution
{
    // Approach: nums is a permutation of 1..n. Count distinct values of
    // nums[i] XOR nums[j] XOR nums[k] for i ≤ j ≤ k. For n ≤ 2 the answer is n;
    // for n ≥ 3 every value in [0, 2^⌈log2(n+1)⌉ − 1] is achievable, so return
    // the next power of two: 1 << (floor(log2(n)) + 1).
    // Complexity: O(1) time and O(1) space (log is O(1) on 32-bit ints).
    public int UniqueXorTriplets(int[] nums)
    {
        int n = nums.Length;
        if (n == 1)
        {
            return 1;
        }
        if (n == 2)
        {
            return 2;
        }
        int b = (int)Math.Floor(Math.Log(n, 2)) + 1;
        return 1 << b;
    }
}

Was this solution helpful?