[LeetCode] 2433. Find The Original Array of Prefix Xor

https://leetcode.com/problems/find-the-original-array-of-prefix-xor/description/

Find The Original Array of Prefix Xor - LeetCode

leetcode - Find The Origianl Array of Prefix XOR

문제 유형: 비트마스킹 / 비트 조작

문제 난이도: Medium

 

 

문제

You are given an integer array pref of size n. Find and return the array arr of size n that satisfies:

• pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i].

Note that ^ denotes the bitwise-xor operation.

It can be proven that the answer is unique.

 

풀이

비트 연산자 ^에 대하여 x^a = b에서 x를 구하려면, x = b ^ a를 구하면 된다.

 

arr[i]는 pref[i] ^ pref[i-1]이다.

 

코드

C++

class Solution {
public:
    vector<int> findArray(vector<int>& pref) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        
        const int n = pref.size();
        vector<int> arr(n);
        arr[0] = pref[0];

        for(int i = 1; i < n; i++) {
            arr[i] = pref[i] ^ pref[i-1];
        }

        return arr;
    }
};