What is a XOR triplet in Number of Unique XOR Triplets I?

A XOR triplet consists of three elements nums[i], nums[j], nums[k] with i <= j <= k, and the triplet value is nums[i] XOR nums[j] XOR nums[k].

Can I use brute force for large arrays?

Brute force works but is inefficient for n up to 10^5. Using prefix XOR or mathematical patterns is recommended.

Do I need to worry about duplicate XOR results?

Yes, counting only unique XOR values is required, so use a set or similar structure to track distinct results.

How does array being a permutation affect the solution?

Permutation ensures all numbers 1 to n are present, affecting maximum and minimum XOR values and helping with pattern recognition.

Which data structures help compute unique XOR triplets efficiently?

Sets for tracking unique results and prefix XOR arrays to reduce repeated XOR calculations are most effective.

#3513

Medium

auto_awesome数组·数学

LeetCode 题解工作台

不同 XOR 三元组的数目 I

给你一个长度为 n 的整数数组 nums ，其中 nums 是范围 [1, n] 内所有数的排列。 XOR 三元组定义为三个元素的异或值 nums[i] XOR nums[j] XOR nums[k] ，其中 i 。返回所有可能三元组 (i, j, k) 中不同的 XOR 值的数量。排…

数组数学位运算

题目描述

给你一个长度为 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⁵
1 <= nums[i] <= n
nums 是从 1 到 n 的整数的一个排列。

lightbulb

解题思路

方法一

1

2

speed

复杂度分析

指标	值
时间	complexity can range from O(n^3) for naive triple iteration to O(n^2) or O(n) using prefix XOR and mathematical insights. Space complexity ranges from O(n) for prefix arrays to O(n^2) for storing unique XOR values depending on the approach.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Notice if candidate identifies the permutation property and its impact on XOR results.
question_mark
Check if they optimize nested loops using prefix XOR or other bitwise properties.
question_mark
Observe whether they consider duplicate elimination and efficient unique counting.

warning

常见陷阱

外企场景

error
Forgetting that triplet indices must satisfy i <= j <= k, causing incorrect counts.
error
Overlooking repeated XOR values and failing to track unique results.
error
Assuming a simple formula for XOR count without considering array permutation constraints.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count unique XOR pairs instead of triplets.
arrow_right_alt
Allow arrays with repeated elements rather than strict permutations.
arrow_right_alt
Compute maximum XOR value among all triplets instead of counting unique results.

help

常见问题

外企场景

继续练习

#3514 不同 XOR 三元组的数目 II #3495 使数组元素都变为零的最少操作次数 #3539 魔法序列的数组乘积之和