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

문제 요약

• 알고리즘 분류: 수학
• 난이도: Medium
• 문제내용:
  • pref이라는 리스트가 주어진다.
  • pref[i] = arr[0] ^ arr[1] ^ arr[2] ...... ^ arr[i]  식처러  arr 0번째 인덱스 부터 i번째 xor연산된 값이다.
  • xor 연산되기 전의 arr를 구하여라
• 사이트 주소: https://leetcode.com/problems/find-the-original-array-of-prefix-xor/description/

문제풀이 

 이번 문제는 xor의 법칙만 알면 쉽게 풀수 있는 문제이다.

위 내용 보면 pref[i] = arr[0] ^ arr[1] ^ arr[2] ...... ^ arr[i]으로 되어 있으면 pref[0] = arr[0]으로 0번째 인덱스는 그대로 넣으면 된다. 그럼 첫번째 인덱스는 pref[1] = arr[0] ^ arr[1]  여기서 부터 보면 된다. xor법칙중 아래와 같은 법칙이 적용이 된다.

X ^ Y = Z → X ^ Z = Y

위와 같은 식이 되기 때문에 pref[1] = arr[0] ^ arr[1] → arr[1] = arr[0]  ^ pref[1]이 된다.

그럼 arr[i] = pref [0] ^ pref [1] ^ pref [2] ...... ^ pref[i] 라는 식을 세울수 있기 때문에 i번째는 연산후 누적시키면 된다. 만약 i번째에서 이전것 연산후 pref[i]하면 시간 초과가 나와서 누적변수에 담아서 처리해야한다.

위와 같은 내용으로 구현하면 시간 복잡도는 O(N)이 나올것이다.

Code

Python

class Solution:
    def findArray(self, pref: list[int]) -> list[int]:

        size = len(pref)
        result = [0 for _ in range(size)]

        result[0] = pref[0]

        value = result[0]  # 누적한 값을 저장 할 변수
        for i in range(1, size):
            result[i] = value ^ pref[i]
            value ^= result[i]  # 누적

        return result

Java

class Solution {
    public int[] findArray(int[] pref) {
        int size = pref.length;
        int[] result = new int[size];

        result[0] = pref[0];

        int value = result[0]; // 누적한 값을 저장 할 변수
        for (int i = 1; i < size; i++) {
            result[i] = value ^ pref[i];
            value ^= result[i]; // 누적
        }

        return result;
    }
}