[leetcode] Single Number

https://leetcode.com/problems/single-number/

 

arr 가 주어진다.

arr 에는 두 쌍의 숫자들과 하나의 숫자가 들어있다.

정렬이 되어있지 않다고 했을 때 쌍이 없이 혼자 있는 수를 찾는 문제이다.

 

2중 for문을 사용하거나

HashMap, HashSet 을 사용하거나,

정렬 한 후에 i, i+1 인덱스를 이용하여 찾아도 일단 풀리긴 한다.

 

하지만 위의 방법들보다 더 획기적인 방법을 사용하면

O(N) 시간에 추가 메모리 없이 문제를 풀 수 있다.

 

 

바로 XOR bit 연산자를 사용하는 것이다.

 

재밌게도, XOR bit 연산자는 똑같은 두 수를 XOR 하면 0이 되어버리고,

0과 어떤 수 n을 XOR 하면 n 이 나온다.

이 점에 착안하여, arr 내에 모든 수를 계속 XOR 해보자.

짝이 있는 수들은 XOR 연산에 의해 0이 되어버리고,

혼자 있는 수는 0과 XOR 되면 혼자 있는 수 그대로 결과로 나온다.

 

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for(int num : nums){
            result = (result^num);
        }
        return result;
    }
}

 

 

이런 문제는 알고 있지 않으면 모르는 문제인 듯.