[Misc][Easy] 136. Single Number

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

 

Q. 주어진 배열에 정수값이 하나만 제외하고 모두 두개씩 들어있다. 이 하나의 값을 찾아라.

 이때 O(N) TC에 추가 메모리를 사용하지 말아라. 

 

Solution. 

 map같은 것을 쓰면 금방 찾을 수 있지만, 문제에서는 leaner TC에 추가 메모리를 사용하지 말라고 했다. 

 따라서 다른 접근이 필요하다. 

 

여기에서 XOR 개념이 필요하다. 

아래에서 보는 바와 같이 XOR 연산은 두 값이 다른 경우 1을 돌려준다. 

 

이 성질을 이용한다.

 

 

 

public int SingleNumber(int[] nums) 
{
    int ret = nums[0];
    for(int q = 1; q < nums.Length; ++q)
    {
        ret ^= nums[q];
    }
    return ret;
}

 

 

 

적절한 결과.