LeetCode (C/C++) 137. Single Number II

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

 

---

풀이

답지를 봤다.

떠오르는 풀이는 많았지만 시간, 공간복잡도의 제약조건이 있어 해당 방법들은 다 사용하지 못 했다.

비트 연산으로 각 자리수마다 해당 숫자가 등장하는 횟수를 확인, 이를 3으로 나눴을 때 값이 존재한다면 이는 3번 나온 수에 포함되지 않으므로 해당 자리수를 답에 더한다.

---

코드

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;

        for (int i = 0; i < 32; i++) {
            int cnt = 0;    
            for (int n : nums)
                cnt += n >> i & 1;
            cnt %= 3;
            ans |= cnt << i;
        }
        return ans;
    }
};