Skip to content

3513. Number of Unique XOR Triplets I

SourceBiweekly Contest 154 Q2DifficultyMediumRating1663

Description

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.

Solutions

Solution 1: Bit Manipulation

Thinking

\(\textit{nums}\) is a permutation of \([1,n]\) and indices may repeat, so the set of triple XORs is determined by \(n\). A cubic enumeration does not match the scale.

For \(n \le 2\) the answer equals \(n\). For \(n \ge 3\) the possible XORs fill \([0, 2^{\lfloor \log_2 n \rfloor + 1} - 1]\), which is \(1 \ll \textit{bitLength}(n)\).

Since \(\textit{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:

\[ \textit{ans} = 1 \ll \textit{bitLength}(n) \]

For example, when \(n = 3\), \(\textit{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)\).

1
2
3
4
class Solution:
    def uniqueXorTriplets(self, nums: List[int]) -> int:
        n = len(nums)
        return n if n <= 2 else 1 << n.bit_length()

1
2
3
4
5
6
class Solution {
    public int uniqueXorTriplets(int[] nums) {
        int n = nums.length;
        return n <= 2 ? n : 1 << (32 - Integer.numberOfLeadingZeros(n));
    }
}

1
2
3
4
5
6
7
class Solution {
public:
    int uniqueXorTriplets(vector<int>& nums) {
        size_t n = nums.size();
        return n <= 2 ? n : 1 << bit_width(n);
    }
};

1
2
3
4
5
6
7
func uniqueXorTriplets(nums []int) int {
    n := len(nums)
    if n <= 2 {
        return n
    }
    return 1 << bits.Len(uint(n))
}

1
2
3
4
5
6
7
function uniqueXorTriplets(nums: number[]): number {
    const n = nums.length;
    if (n <= 2) {
        return n;
    }
    return 1 << (32 - Math.clz32(n));
}

1
2
3
4
5
6
7
8
9
impl Solution {
    pub fn unique_xor_triplets(nums: Vec<i32>) -> i32 {
        let length = nums.len() as i32;
        if length < 3 {
            return length;
        }
        1 << (length.ilog2() + 1)
    }
}

Comments