LeetCode 3922: Find X Value of Array II (Bitwise OR with Queries)

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

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

LeetCode 3922 prefix and suffix OR diagram

English

For each index i, remove nums[i] and compute OR of remaining numbers. Prefix OR + suffix OR gives O(n).

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

中文

对每个 i 删除 nums[i] 后求其余元素 OR，利用前缀 OR 与后缀 OR 可把复杂度降到 O(n)。

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

Comments