M3513.不同XOR三元组的数目I

bit manipulation, https://leetcode.cn/problems/number-of-unique-xor-triplets-i/

给你一个长度为 n 的整数数组 nums，其中 nums 是范围 [1, n] 内所有数的排列。

XOR 三元组 定义为三个元素的异或值 nums[i] XOR nums[j] XOR nums[k]，其中 i <= j <= k。

返回所有可能三元组 (i, j, k) 中不同的 XOR 值的数量。

排列是一个集合中所有元素的重新排列。

示例 1：

输入： nums = [1,2]

输出： 2

解释：

所有可能的 XOR 三元组值为：

(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

不同的 XOR 值为 {1, 2}，因此输出为 2。

示例 2：

输入： nums = [3,1,2]

输出： 4

解释：

可能的 XOR 三元组值包括：

(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

不同的 XOR 值为 {0, 1, 2, 3}，因此输出为 4。

提示：

1 <= n == nums.length <= 10^5
1 <= nums[i] <= n
nums 是从 1 到 n 的整数的一个排列。

Thought for 38 seconds

The problem asks to count distinct XOR values from all possible triples (i, j, k) where i<=j<=k. Since XOR is commutative, this turns into checking the XOR of sets of triplets from the numbers 1 to n (since nums is a permutation of 1..n). Each value can appear multiple times due to repetition, so it's a multiset problem. I'll need to come up with an efficient way to generate these distinct XOR results without checking every triplet brute force, especially since n can be as large as 100,000.
The task involves counting distinct XOR results from triplets (i, j, k). Since indices are sorted, repetition is allowed, but values are distinct, so the triples can repeat values at the same index. The important observation is that the possible XOR results come from:
Values from v^v^v = v
Distinct pairs ∀ v^v^u or v^u^u
XOR combinations from three distinct values v^u^w for v < u < w
Ultimately, the answer depends purely on n, involving all numbers from 1 to n and the distinct results from XOR of distinct triplets.
The task is to calculate how many distinct XOR results come from triplets of distinct numbers in the range 1..n. From the examples, I see that for n=2 the answer is 2, and for n=3 the answer is 4.
The goal is to count the distinct XORs for triplets (v1, v2, v3), excluding those that are already part of the range 1..n. I'll compute all potential XORs for small values of n and look for a pattern. Exploring up to n=50 should help identify any regularity. The formula might emerge from this brute-force approach.
Analyzed
from itertools import combinations
def compute(n):
    S = set(range(1, n+1))
    for a,b,c in combinations(range(1, n+1),3):
        S.add(a^b^c)
    return len(S)

results = {n: compute(n) for n in range(1, 51)}
results
{1: 1,
 2: 2,
 3: 4,
 4: 8,
 5: 8,
 6: 8,
 7: 8,
 8: 16,
 9: 16,
 10: 16,
 11: 16,
 12: 16,
 13: 16,
 14: 16,
 15: 16,
 16: 32,
 17: 32,
 18: 32,
 19: 32,
 20: 32,
 21: 32,
 22: 32,
 23: 32,
 24: 32,
 25: 32,
 26: 32,
 27: 32,
 28: 32,
 29: 32,
 30: 32,
 31: 32,
 32: 64,
 33: 64,
 34: 64,
 35: 64,
 36: 64,
 37: 64,
 38: 64,
 39: 64,
 40: 64,
 41: 64,
 42: 64,
 43: 64,
 44: 64,
 45: 64,
 46: 64,
 47: 64,
 48: 64,
 49: 64,
 50: 64}
For small values of n, the number of distinct XOR results seems to follow a pattern. For instance, when n=2, the answer is 2, and when n=3, the answer is 4. I need to focus on computing XORs for all distinct triples (v1, v2, v3) from the range 1 to n. The challenge is to determine the count of distinct XOR results and not list them, especially given that n can go up to 100,000. I'll test smaller values to identify any pattern for efficiency.
By brute-forcing values up to n = 50, I can observe a pattern in the number of distinct XOR results. For small values of n, the results seem to follow powers of two. For example: n=1 gives 1, n=2 gives 2, n=3 gives 4, and then powers of two continue at n=4, 8, 16, etc. The key observation here suggests that S(n) is the next power of two greater than n for n ≥ 2. Special handling is needed for n=1, where the result is 1.
Done

下面是一种 O(1) 时间的解法。注意到：

当 n<3 时，数组长度小于 3，三元组最多只能是重复元素，因此能得到的异或值仅为数组中已有的元素个数，即直接返回 n。
当 n>=3 时，所有可能的三元组（含三种不同情况下：v,v,v；v,v,u；u,v,w 三个互不相同）所能覆盖的异或结果，恰好是从 0 到 $‘ 2^{⌊ l o g ₂ n ⌋ + 1} - 1 ‘$ 的所有整数。因此不同异或值的数量是
$2^{⌊ \log_{2} n ⌋ + 1}$ .

利用 Python 的 int.bit_length() 方法可以快速计算出 $⌊ \log_{2} n ⌋ + 1$ ，代码如下：

python

from typing import List

class Solution:
    def uniqueXorTriplets(self, nums: List[int]) -> int:
        n = len(nums)
        # 若长度 < 3，三元组只能是重复元素，异或结果即数组内元素，种类为 n
        if n < 3:
            return n
        return 1 << n.bit_length()

复杂度分析：

时间复杂度： $O (1)$
空间复杂度： $O (1)$

这种方法不需要实际枚举任何三元组，也不受 n 最大值（ $10^{5}$ ）的影响，直接通过位运算得到答案。

M3513.不同XOR三元组的数目I ​

M3513.不同XOR三元组的数目I