LeetCode 3923: Find X Value of Array III (Bitwise AND with Queries)

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

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

LeetCode 3923 prefix and suffix AND diagram

English

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

class Solution {
    public int[] findXValue(int[] nums) {
        int n = nums.length;
        int allOnes = ~0;
        int[] left = new int[n], right = new int[n], ans = new int[n];
        left[0] = allOnes;
        right[n - 1] = allOnes;
        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)
    allOnes := ^0
    left := make([]int, n)
    right := make([]int, n)
    ans := make([]int, n)
    left[0], right[n-1] = allOnes, allOnes
    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();
        int allOnes = ~0;
        vector<int> left(n), right(n), ans(n);
        left[0] = allOnes;
        right[n - 1] = allOnes;
        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)
        all_ones = (1 << 31) - 1
        left = [0] * n
        right = [0] * n
        ans = [0] * n
        left[0] = all_ones
        right[-1] = all_ones
        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;
  const ALL_ONES = 0x7fffffff;
  const left = Array(n).fill(0), right = Array(n).fill(0), ans = Array(n).fill(0);
  left[0] = ALL_ONES;
  right[n - 1] = ALL_ONES;
  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] 后求其余元素按位与，利用前缀 AND 与后缀 AND 可把复杂度降到 O(n)。

class Solution {
    public int[] findXValue(int[] nums) {
        int n = nums.length;
        int allOnes = ~0;
        int[] left = new int[n], right = new int[n], ans = new int[n];
        left[0] = allOnes;
        right[n - 1] = allOnes;
        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)
    allOnes := ^0
    left := make([]int, n)
    right := make([]int, n)
    ans := make([]int, n)
    left[0], right[n-1] = allOnes, allOnes
    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();
        int allOnes = ~0;
        vector<int> left(n), right(n), ans(n);
        left[0] = allOnes;
        right[n - 1] = allOnes;
        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)
        all_ones = (1 << 31) - 1
        left = [0] * n
        right = [0] * n
        ans = [0] * n
        left[0] = all_ones
        right[-1] = all_ones
        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;
  const ALL_ONES = 0x7fffffff;
  const left = Array(n).fill(0), right = Array(n).fill(0), ans = Array(n).fill(0);
  left[0] = ALL_ONES;
  right[n - 1] = ALL_ONES;
  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