SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

Given an array arr of integers and a list of queries, where each query is defined as [left, right], the goal is to find the XOR of elements between the indices left and right (inclusive) for each query.

Intuition

Using a prefix XOR array allows us to efficiently calculate the XOR of any subarray. The key observation is that if you have the XOR of the range from 0 to right, you can subtract out the XOR of the range from 0 to left-1 to get the XOR of the range from left to right.

Approach

1. Precompute the prefix XOR array pre where pre[i] represents the XOR of elements from index 0 to i.
2. For each query [left, right]:
   • If left is 0, the answer is pre[right].
   • Otherwise, the answer is pre[right] ^ pre[left-1].
3. Collect results and return them.

Complexity

Time Complexity:

O(n + q) where n is the length of arr and q is the number of queries. Building the prefix XOR array takes O(n), and answering each query takes constant time.

Space Complexity:

O(n) for storing the prefix XOR array.

Code

C++

class Solution {
public:
    std::vector<int> xorQueries(std::vector<int>& arr,
                                std::vector<std::vector<int>>& queries) {
        int n = arr.size();
        std::vector<int> pre(n);
        pre[0] = arr[0];

        // Compute prefix XOR array
        for (int i = 1; i < n; i++) {
            pre[i] = pre[i - 1] ^ arr[i];
        }

        std::vector<int> res;

        // Answer each query
        for (const auto& query : queries) {
            int left = query[0], right = query[1];
            if (left == 0) {
                res.push_back(pre[right]);
            } else {
                res.push_back(pre[right] ^ pre[left - 1]);
            }
        }

        return res;
    }
};

Python

class Solution:
    def xorQueries(self, arr, queries):
        n = len(arr)
        pre = [0] * n
        pre[0] = arr[0]

        # Compute prefix XOR array
        for i in range(1, n):
            pre[i] = pre[i - 1] ^ arr[i]

        res = []

        # Answer each query
        for left, right in queries:
            if left == 0:
                res.append(pre[right])
            else:
                res.append(pre[right] ^ pre[left - 1])

        return res

Java

class Solution {
    public int[] xorQueries(int[] arr, int[][] queries) {
        int n = arr.length;
        int[] pre = new int[n];
        pre[0] = arr[0];

        // Compute prefix XOR array
        for (int i = 1; i < n; i++) {
            pre[i] = pre[i - 1] ^ arr[i];
        }

        int[] res = new int[queries.length];

        // Answer each query
        for (int i = 0; i < queries.length; i++) {
            int left = queries[i][0], right = queries[i][1];
            if (left == 0) {
                res[i] = pre[right];
            } else {
                res[i] = pre[right] ^ pre[left - 1];
            }
        }

        return res;
    }
}

JavaScript

var xorQueries = function (arr, queries) {
    const n = arr.length;
    const pre = new Array(n);
    pre[0] = arr[0];

    // Compute prefix XOR array
    for (let i = 1; i < n; i++) {
        pre[i] = pre[i - 1] ^ arr[i];
    }

    const res = [];

    // Answer each query
    for (const [left, right] of queries) {
        if (left === 0) {
            res.push(pre[right]);
        } else {
            res.push(pre[right] ^ pre[left - 1]);
        }
    }

    return res;
};