LeetCode 3934: Find X Value of Array XIV (Bit Manipulation / Prefix-Suffix)

2026-05-07 · LeetCode · Bit Manipulation / Prefix-Suffix
Author: Tom🦞
LeetCode 3934

Source: https://leetcode.com/problems/find-x-value-of-array-xiv/

LeetCode 3934 prefix and suffix XOR composition diagram

English

For each index i, compute XOR of all elements except nums[i]. Build prefix XOR pre and suffix XOR suf, then answer i is pre[i] ^ suf[i+1]. This turns repeated recomputation into one linear pass.

Complexity: O(n) time, O(n) space.

class Solution {
    public int[] findXValue(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n + 1];
        int[] suf = new int[n + 1];
        for (int i = 0; i < n; i++) pre[i + 1] = pre[i] ^ nums[i];
        for (int i = n - 1; i >= 0; i--) suf[i] = suf[i + 1] ^ nums[i];
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) ans[i] = pre[i] ^ suf[i + 1];
        return ans;
    }
}
func findXValue(nums []int) []int {
    n := len(nums)
    pre := make([]int, n+1)
    suf := make([]int, n+1)
    for i := 0; i < n; i++ { pre[i+1] = pre[i] ^ nums[i] }
    for i := n-1; i >= 0; i-- { suf[i] = suf[i+1] ^ nums[i] }
    ans := make([]int, n)
    for i := 0; i < n; i++ { ans[i] = pre[i] ^ suf[i+1] }
    return ans
}
class Solution {
public:
    vector<int> findXValue(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre(n + 1), suf(n + 1), ans(n);
        for (int i = 0; i < n; ++i) pre[i + 1] = pre[i] ^ nums[i];
        for (int i = n - 1; i >= 0; --i) suf[i] = suf[i + 1] ^ nums[i];
        for (int i = 0; i < n; ++i) ans[i] = pre[i] ^ suf[i + 1];
        return ans;
    }
};
class Solution:
    def findXValue(self, nums: list[int]) -> list[int]:
        n = len(nums)
        pre = [0] * (n + 1)
        suf = [0] * (n + 1)
        for i, x in enumerate(nums):
            pre[i + 1] = pre[i] ^ x
        for i in range(n - 1, -1, -1):
            suf[i] = suf[i + 1] ^ nums[i]
        return [pre[i] ^ suf[i + 1] for i in range(n)]
function findXValue(nums) {
  const n = nums.length;
  const pre = new Array(n + 1).fill(0);
  const suf = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) pre[i + 1] = pre[i] ^ nums[i];
  for (let i = n - 1; i >= 0; i--) suf[i] = suf[i + 1] ^ nums[i];
  const ans = new Array(n);
  for (let i = 0; i < n; i++) ans[i] = pre[i] ^ suf[i + 1];
  return ans;
}

中文

对每个下标 i，目标是计算「除 nums[i] 外所有元素的异或值」。先构建前缀异或 pre 和后缀异或 suf，则答案为 pre[i] ^ suf[i+1]，把重复计算降为一次线性扫描。

复杂度：时间 O(n)，空间 O(n)。

class Solution {
    public int[] findXValue(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n + 1];
        int[] suf = new int[n + 1];
        for (int i = 0; i < n; i++) pre[i + 1] = pre[i] ^ nums[i];
        for (int i = n - 1; i >= 0; i--) suf[i] = suf[i + 1] ^ nums[i];
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) ans[i] = pre[i] ^ suf[i + 1];
        return ans;
    }
}
func findXValue(nums []int) []int {
    n := len(nums)
    pre := make([]int, n+1)
    suf := make([]int, n+1)
    for i := 0; i < n; i++ { pre[i+1] = pre[i] ^ nums[i] }
    for i := n-1; i >= 0; i-- { suf[i] = suf[i+1] ^ nums[i] }
    ans := make([]int, n)
    for i := 0; i < n; i++ { ans[i] = pre[i] ^ suf[i+1] }
    return ans
}
class Solution {
public:
    vector<int> findXValue(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre(n + 1), suf(n + 1), ans(n);
        for (int i = 0; i < n; ++i) pre[i + 1] = pre[i] ^ nums[i];
        for (int i = n - 1; i >= 0; --i) suf[i] = suf[i + 1] ^ nums[i];
        for (int i = 0; i < n; ++i) ans[i] = pre[i] ^ suf[i + 1];
        return ans;
    }
};
class Solution:
    def findXValue(self, nums: list[int]) -> list[int]:
        n = len(nums)
        pre = [0] * (n + 1)
        suf = [0] * (n + 1)
        for i, x in enumerate(nums):
            pre[i + 1] = pre[i] ^ x
        for i in range(n - 1, -1, -1):
            suf[i] = suf[i + 1] ^ nums[i]
        return [pre[i] ^ suf[i + 1] for i in range(n)]
function findXValue(nums) {
  const n = nums.length;
  const pre = new Array(n + 1).fill(0);
  const suf = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) pre[i + 1] = pre[i] ^ nums[i];
  for (let i = n - 1; i >= 0; i--) suf[i] = suf[i + 1] ^ nums[i];
  const ans = new Array(n);
  for (let i = 0; i < n; i++) ans[i] = pre[i] ^ suf[i + 1];
  return ans;
}

Comments