LeetCode 3932: Find X Value of Array XII (Bit Manipulation / Prefix-Suffix)

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

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

Prefix XOR from left and suffix XOR from right combine into all-except-self XOR

English

To compute each position's X value efficiently, we avoid recomputing XOR of all remaining elements for every index. Build a prefix XOR array and a suffix XOR array. Then for index i, the XOR of all elements except nums[i] is prefix[i-1] ^ suffix[i+1]. This gives an O(n) solution with O(n) extra 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 ? 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 := 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 ? 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
        pre[0] = nums[0]
        for i in range(1, n):
            pre[i] = pre[i - 1] ^ nums[i]
        suf[n - 1] = nums[n - 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 = pre[i - 1] if i > 0 else 0
            right = suf[i + 1] if i + 1 < n else 0
            ans[i] = left ^ right
        return ans
var findXValue = function(nums) {
  const n = nums.length;
  const pre = new Array(n).fill(0);
  const suf = new 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];
  const ans = new Array(n).fill(0);
  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;
};

中文

如果对每个位置都重新计算“除自己以外所有元素异或值”，会变成 O(n²)。更好的做法是预处理前缀异或和后缀异或。对于下标 i，答案就是 pre[i-1] ^ suf[i+1]。这样每个位置 O(1) 得到结果，总复杂度 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 ? 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 := 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 ? 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
        pre[0] = nums[0]
        for i in range(1, n):
            pre[i] = pre[i - 1] ^ nums[i]
        suf[n - 1] = nums[n - 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 = pre[i - 1] if i > 0 else 0
            right = suf[i + 1] if i + 1 < n else 0
            ans[i] = left ^ right
        return ans
var findXValue = function(nums) {
  const n = nums.length;
  const pre = new Array(n).fill(0);
  const suf = new 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];
  const ans = new Array(n).fill(0);
  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