[Bit Manipulation][Easy] 136. Single Number

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

LeetCode - The World's Leading Online Programming Learning Platform

 

Q. 주어진 배열 nums에서 단하나의 원소를 제외하고 모든 원소는 2회씩 출현한다.

이때 이 한번 출현하는 값을 찾아라. 

TC를 O(N)으로 추가 메모리를 사용치 말아라. 

 

Solution. 

 XOR의 특성을 알고 있다면 어렵지 않게 풀수 있는 문제. 

 

위 그림에서 보다시피, 

input의 두 bit가 다를때만 결과가 1이 된다. 

 

따라서 A xor A 는 언제나 0 이 된다. 

하지만, A xor B xor A 는 어떨까?

테스트 해 보자. 

 

A: 10

B : 01

 

A xor B = 11

11 xor A = 01 

 

결과에서 보듯이 A xor B xor A = B 가 나옴을 알수 있다. 

(즉, A xor A xor B 와 같은 결과. )

즉, 곱셉처럼 교환법칙이 성립하는 것이다.

따라서 그냥 이를 적용하여 로직을 만들면 된다. 

 

int singleNumber(vector<int>& nums)
{
    int ret = nums[0];
    for (int q = 1; q < nums.size(); ++q)
        ret = ret ^ nums[q];

    return ret;
}

 

 

결과.