[Hackerrank] Week5 - Sansa and XOR

문제

비트 연산을 묻는 문제이다.
리스트의 모든 요소의 XOR 값을 구하는 문제이므로 리스트의 부분집합을 모두 구한다음 계산할 수도 있지만, 그렇게 한다면 너무 많은 시간이 소요된다.

예제에 주어진 리스트 [3, 4, 5]의 XOR연산을 풀어써본다면

3^4^5^(3^4)^(4^5)^(3^4^5)가 된다는걸 알 수 있다

자기 자신을 XOR를 한다면 0이 되므로 짝수 개의 원소는 소거할 수 있다.

즉, 3^5가 된다.

다시 말해 짝수 인덱스의 원소는 배제할 수 있다.

코드

def sansaXor(arr):
    a = 0
    if len(arr) % 2 == 0: // 리스트의 길이가 짝수면 0
        return 0

    for i in range(0, len(arr) + 1, 2):
        a ^= arr[i]

    return a