1720-kir3i.md

1720. Decode XORed Array

Solution

• 시간복잡도: O(N)

• 알고리즘

  구현

• 풀이설명

  XOR의 특성을 이용하면 됩니다. original array의 첫번째 값인 first가 주어졌으므로 a XOR b = c라고 할 때 c XOR b = a인 점을 이용해서 encoded를 순회하며 original array를 구할 수 있습니다.

• 소스코드

  • C++

    class Solution {
    public:
        vector<int> decode(vector<int>& encoded, int first) {
            vector<int> ans = {first};
            for(const int &x: encoded)
                ans.push_back(ans.back()^x);
            return ans;
        }
    };

  • Python

    class Solution:
        def decode(self, encoded, first):
            ans = [first]
            for x in encoded:
                ans.append(ans[-1]^x)
            return ans

  • Java

    class Solution {
        public int[] decode(int[] encoded, int first) {
            int[] ans = new int[encoded.length+1];
            ans[0] = first;
            for(int i=0; i<encoded.length; i++)
                ans[i+1] = ans[i]^encoded[i];
            return ans;
        }
    }