[LeetCode] 2683. Neighboring Bitwise XOR

https://leetcode.com/problems/neighboring-bitwise-xor/description/

leetcode - Neighboring Bitwise XOR

문제 유형: 비트마스킹, 그리디

문제 난이도: Medium

 

문제

A 0-indexed array derived with length n is derived by computing the bitwise XOR (⊕) of adjacent values in a binary array original of length n.

Specifically, for each index i in the range [0, n - 1]:

• If i = n - 1, then derived[i] = original[i] ⊕ original[0].
• Otherwise, derived[i] = original[i] ⊕ original[i + 1].

Given an array derived, your task is to determine whether there exists a valid binary array original that could have formed derived.

Return true if such an array exists or false otherwise.

• A binary array is an array containing only 0's and 1's

0-indexed의 n길이 binary 배열 derived가 주어진다.

original배열 기반으로 다음의 규칙으로 생성한 것이다:

i = n-1에 대해서, derived[i] = original[i] ⊕ original[0] 이다.

이외에는 derived[i] = original[i] ⊕ original[i+1]. 이다.

 

original배열로부터 derived를 만들 수 있는지 구하시오.

 

풀이

original을 복구해보면서 복구하는 과정에서 오류가 없으면 된다.

맨 오른쪽 비트를0이라고 가정하고, 0인덱스의 원본값을 derived[0]을 기반으로 불러온다.

original[i]를 이전값으로부터 derived[i]와 구할 수 있다.

배열을 다 순회하고 나서의 original[i]와 맨 오른쪽 최초설정한 비트가 같으면, 정상적으로 한 바퀴를 돌았으므로 true이다.

 

맨 오른쪽이 1이라고도 가정하고 똑같이 한다.

 

두 가지 경우 모두 실패시 false를 반환해주면 된다.

 

코드

C++

class Solution {
public:
    bool doesValidArrayExist(vector<int>& derived) {
        int n = derived.size();

        int lsb = 0;
        int curr = lsb == derived[0]? 0:1;
        for(int i = 1; i < n; ++i) {
            if(curr == derived[i]) curr = 0;
            else curr = 1;
        }
        if(lsb == curr) return true;

        lsb = 1;
        curr = lsb == derived[0]? 0:1;
        for(int i = 1; i < n; ++i) {
            if(curr == derived[i]) curr = 0;
            else curr = 1;
        }
        if(lsb == curr) return true;

        return false;
    }
};