O(n) + constant space solution. Count digits.


  • 0
    L

    Algo: Count digit. The answer consists of the digits which doesn't appear three times.
    Be careful about negative number. Counting in binary bit is a better solution I found in Discuss.

    class Solution {
    public:
        int singleNumber(int A[], int n) {
            assert(n > 0);
    		int dig[10][20];
    		fill(dig[0], dig[10], 0);
    		for (int i = 0; i < n; ++i) {
    			int x = A[i];
    			int index = 0;
    			do {
    				++dig[index++][x%10 + 10];
    				x /= 10;
    			} while (x);
    		}
    		int ans = 0;
    		for (int pos = 9; pos >= 0; --pos) {
    			for (int d = 0; d < 20; ++d) if (dig[pos][d] % 3) {
    				ans = ans * 10 + d - 10;
    			}
    		}
    		return ans;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.