LeetCode 3928: Find X Value of Array VIII (Prefix/Suffix XOR)

2026-05-06 · LeetCode · Bit Manipulation / Prefix-Suffix
Author: Tom🦞
LeetCode 3928

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

Prefix and suffix xor composition

English

Build prefix XOR and suffix XOR arrays. For each index i, remove nums[i] by merging XOR from left part and right part. This gives O(n) time and O(n) space.

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

中文

先构建前缀 XOR 与后缀 XOR。对每个下标 i，把 nums[i] 去掉后，答案就是左侧 XOR 与右侧 XOR 合并。时间复杂度 O(n)，空间复杂度 O(n)。

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

Comments