[OJ.leetcode] single-number-ii

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

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

/* 사고의 전환이 필요. 일종의 트릭인데, array를 element 단위보다 더 작은 bit level 에서 볼 수 있고 bit level operation을 할 수 있느냐를 보는 문제. "Given an array of integers, every element appears twice except for one. Find that single one." 와도 거의 같은 문제 ex 정수 12 = 1100 이고, A={12,12,12,1} == {1100,1100,1100,0001} 이면 맨 오른쪽 bit의 경우 1이 3회 반복되므로 이를 mod 3할 경우 0이 된다. 마찬가지로 두번째비트의 경우도 0, 3번째비트의 경우 모두 0이므로 0 네번째 비트의 경우 single one인 1만 1비트를 가지고 있으므로 mod 3의 경우 1이된다. 즉 모든 수의 비트를 count하여 mod3을 하면 3회 나타나는 수의 경우 모두 0이 되고, 1회 나타나는 수의 경우 그자신의 값으로 세팅된다. 이를 이용하면 어떤 정수가 n회씩 나타나는 정수 배열중 k회 나타나는 정수 1개의 값을 리턴하라. 라는 문제로 일반화 할 수 있다. time complexity : O(kn) (k는 32 bit or 64 bit) */ class Solution { public: int singleNumber(int A[], int n) { int res = 0; for(int i=0; i< sizeof(int)*8 ; ++i) { int set = 0; for(int j=0; j<n ; j++) { if(A[j]>>i & 1) { ++set; } } res |= (set % 3)<<i; } return res; } };