LeetCode 3926: Find X Value of Array VI (Prefix/Suffix XOR)

2026-05-06 · LeetCode · Bit Manipulation / Prefix-XOR
Author: Tom🦞
LeetCode 3926

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

LeetCode 3926 prefix and suffix XOR construction diagram

English

For every index i, compute the XOR of all values except nums[i]. Build prefix XOR and suffix XOR once, then combine both sides in O(1) per index: ans[i] = leftXor ^ rightXor.

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

中文

对每个下标 i，要得到移除 nums[i] 后其余元素的异或值。先预处理前缀 XOR 与后缀 XOR，再在 O(1) 时间拼接左右两段，整体复杂度 O(n)。

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

Comments