Single Number Solutions in C++

// Source : https://oj.leetcode.com/problems/single-number/
// Author : Hao Chen
// Date   : 2014-06-17



#include <stdio.h>
// This is classical interview question
// As we know, the same number XOR together will be 0,
// So, XOR all of numbers, the result is the number which only appears once. 
int singleNumber(int A[], int n) {
    int s = 0;
    for(int i=0; i<n; i++){
        s = s^A[i];
    }
    return s;
}

int main()
{
    int a[]={1,1,2,2,3};
    printf("%d\n", singleNumber(a,5));
    return 0;
}

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

/// Source : https://leetcode.com/problems/single-number/
/// Author : liuyubobobo
/// Time   : 2016-12-05

#include <iostream>
#include <vector>
#include <unordered_set>
#include <cassert>

using namespace std;


/// Using hashtable to find the one
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int singleNumber(vector<int>& nums) {

        assert(nums.size()%2 == 1);

        unordered_set<int> hashtable;
        for(int i = 0 ; i < nums.size() ; i ++)
            if(hashtable.find(nums[i]) == hashtable.end())
                hashtable.insert(nums[i]);
            else
                hashtable.erase(nums[i]);

        assert(hashtable.size() == 1);
        return *hashtable.begin();
    }
};


int main() {

    vector<int> nums = {0, 0, 1, 1, 2};
    cout << Solution().singleNumber(nums) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/single-number/
/// Author : liuyubobobo
/// Time   : 2018-06-11

#include <iostream>
#include <vector>
#include <unordered_set>
#include <cassert>
#include <numeric>

using namespace std;


/// Using the sum of vector and the sum of set
/// mathematically get the result
///
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int singleNumber(vector<int>& nums) {

        assert(nums.size()%2 == 1);

        unordered_set<int> set;
        for(int num: nums)
            set.insert(num);

        return 2 * accumulate(set.begin(), set.end(), 0) - accumulate(nums.begin(), nums.end(), 0);
    }
};


int main() {

    vector<int> nums = {0, 0, 1, 1, 2};
    cout << Solution().singleNumber(nums) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/single-number/
/// Author : liuyubobobo
/// Time   : 2016-12-05


#include <iostream>
#include <vector>
#include <unordered_set>
#include <cassert>
#include <stdexcept>

using namespace std;


/// Using the attribution of xor operation:
/// a ^ 0 = a
/// a ^ a = 0
///
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int singleNumber(vector<int>& nums) {

        assert(nums.size()%2 == 1);

        int res = 0;
        for(int i = 0 ; i < nums.size() ; i ++)
            res ^= nums[i];
        return res;
    }
};


int main() {

    vector<int> nums = {0, 0, 1, 1, 2};
    cout << Solution().singleNumber(nums) << endl;

    return 0;
}