[LeetCode] 1310. XOR Queries of a Subarray

https://leetcode.com/problems/xor-queries-of-a-subarray/description/?envType=daily-question&envId=2024-09-13

leetcode - XOR Queries of a Subarray

문제 유형 : 비트마스킹, 부분합

문제 난이도 : Medium

 

문제

You are given an array arr of positive integers. You are also given the array queries where queries[i] = [lefti, righti].

For each query i compute the XOR of elements from lefti to righti (that is, arr[lefti] XOR arr[lefti + 1] XOR ... XOR arr[righti] ).

Return an array answer where answer[i] is the answer to the ith query.

 

정수 배열 arr을 받는다. 2D배열 queries를 받는데, queries[i] = [left, right]를 받는다.

각 queries의 요소들을 읽고, arr[left] XOR arr [left+1] XOR ... XOR arr[right]의 값들을 배열에 순서대로 담아서 반환하시오.

 

풀이

무식하게 풀어도 통과하긴 하는데, 효율적으로 풀 방법이 있다.

바로 부분 xor합 세트를 만드는 것이다.

table[i] = arr[0]부터 arr[i]까지 XOR한 누적값이라고 저장하자.

 

그 뒤 쿼리를 읽으면서, 

left가 0이면 table[right]를 바로 반환하면 되고,

아니면 table[right] ^ table[left-1](left전까지의 xor을 다시 꺼야하므로)를 하면,

arr[left]부터 arr[right]까지 XOR한 값이 된다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        vector<int> table(arr.size());
        vector<int> ans;
        table[0] = arr[0];
        for(int i = 1; i < arr.size(); ++i) {
            table[i] = table[i-1] ^ arr[i];
        }

        for(const auto &query : queries) {
            int from = query[0];
            int to = query[1];
            
            if(from == 0) ans.push_back(table[to]);
            else ans.push_back(table[from-1] ^ table[to]);
        }
        return ans;
    }
};

Go

func xorQueries(arr []int, queries [][]int) []int {
    ans := make([]int, len(queries))
    table := make([]int, len(arr))
    table[0] = arr[0]

    for i := 1; i < len(arr); i++ {
        table[i] = table[i-1] ^ arr[i]
    }

    for i, query := range queries {
        from := query[0]
        to := query[1]

        if from == 0 {
            ans[i] = table[to]
        } else {
            ans[i] = table[to] ^ table[from-1]
        }
    }

    return ans
}