Day 71, ##, Single Number, Single Number II

Single Number
Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
------------------------------------------------------------
XOR
we know A^A = 0 and A^A^B  == A^B^A == B;

class Solution {
public:
    int singleNumber(int A[], int n) {
        int ret = 0;
        for (int i = 0; i < n; i++) {
            ret = ret ^ A[i];
        }
        return ret;
    }
};

Update on Dec-26-2014
other solutions:
#1 hashmap
#2 sort
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?
-----------------------------------------------------------------
Solution #1
Consider all numbers in binary format. Using an array to contain the result of bits count mod by 3

class Solution {
public:
    int singleNumber(int A[], int n) {
        vector<int> v(32,0);
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            for (int j = 0; j < n; j++) {
                if ((A[j] >> i) & 1) {
                    v[i] = (v[i] + 1) % 3;
                }
            }
            ret |= (v[i] << i); 
        }
        return ret;
    }
};

Update on Dec-26-2014
vector can be replaced with a single variable
Solution #2
one contains bits that are shown once, two is for twice.
on

class Solution {
public:
    int singleNumber(int A[], int n) {
        int one = 0, two = 0, three = 0;
        for (int i = 0; i < n; i++) {
            two = two | (one & A[i]); // plus bits shown in both one and A[i], now two may contain bits that show 3 times 
            one = one ^ A[i]; // discard bits that have been shown twice
            three = ~ (one & two); // find bits that are in both one and two, then invert them
            
            // discard bits that have been shown 3 times
            one = one & three; 
            two = two & three;
        }
        return one;
    }
};

COME_BACK
https://leetcode.com/discuss/6632/challenge-me-thx

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0, two = 0;
        for (int i = 0; i < nums.size(); i++) {
            one = ~two & (nums[i] ^ one);
            two = ~one & (nums[i] ^ two);
        }
        
        return one;
    }
};