(Python3) - LeetCode (Medium) : 2683. Neighboring Bitwise XOR

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

xor의 특성을 이용한 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

📑 derived의 xor한 결과를 저장할 xor_sum를 선언 후 0으로 초기화합니다.

📔 풀이과정

📑 derived 배열의 xor 특성

`derived` 배열은 인접한 `original` 배열의 xor 결과로 정의됩니다:

$$derived[i] = original[i] \oplus original[(i+1) \mod n]$$

derived 배열의 모든 값을 $\oplus$하면:

$$derived[0] \oplus derived[1] \oplus \dots \oplus derived[n-1]$$

이를 original 배열로 치환하면: $$(original[0] \oplus original[1]) \oplus (original[1] \oplus original[2]) \oplus \dots \oplus (original[n-1] \oplus original[0])$$

 

이 됩니다.

📑 XOR결과와 유효성의 관계
따라서 derived 배열의 모든 값을 xor 한 결과가 0 이라면 원형 관계를 만족하는 original 배열을 만들 수 있습니다.
$$derived[n-1] = original[n-1] \oplus original[0]$$
반대로 xor 결과가 0이 아니라면 원형 관계를 만족하는 original 배열을 만들 수 없습니다.

 

📑 풀이과정

derived의 모든 원소를 xor한 값을 xor_sums에 저장합니다.

 

📑 시간 복잡도: 배열 하나에 대한 for loop를 수행하므로 O(N)입니다.

 

📑 공간 복잡도: 추가 변수는 xor_sums하나이므로 O(1)입니다.

📔 정답 출력 | 반환

xor_sums가 0이라면 원형으로 계산가능한 원래 배열을 만들 수 있으므로 True를, 아니라면 False를 반환합니다.

---

📕 Code

📔 Python3

class Solution:
    def doesValidArrayExist(self, derived: List[int]) -> bool:
        xor_sums = 0
        for num in derived:
            xor_sums ^= num
        return xor_sums == 0

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.