Missing Number Solutions in C++

// Source : https://leetcode.com/problems/missing-number/
// Author : Hao Chen
// Date   : 2015-10-22



class Solution {
public:
    // This problem can be converted to the classic problem --
    //    `There is an array, all of numbers except one appears twice, and that one only appears once`
    // It means, we can combin two arrays together, one is [1..n], another one is `nums`.
    // Then, you know, we can use the XOR solve this problem.
    
    int missingNumber01(vector<int>& nums) {
        int result = 0;
        for(int i=0; i<nums.size(); i++){
            result ^=  nums[i];
        }
        for(int i=1; i<=nums.size(); i++){
            result ^=(i);
        }
        return result;
    }
    
    // We can simplify the previous solution as below
    int missingNumber02(vector<int>& nums) {
        int result = 0;
        for(int i=0; i<nums.size(); i++){
            result = result ^ (i+1) ^ nums[i];
        }
        return result;
    }
    
    int missingNumber(vector<int>& nums) {
        //By Leetcode running result, they all are same performance
        return missingNumber02(nums); //36ms
        return missingNumber01(nums); //36ms
    }
};

/// Source : https://leetcode.com/problems/missing-number/description/
/// Author : liuyubobobo
/// Time   : 2017-11-10

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


/// Sort and Check
/// Time Complexity:  O(nlogn)
/// Space Complexity: O(1)
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int res = -1;
        for(int i = 0 ; i < nums.size() ; i ++)
            if(nums[i] != i){
                res = i;
                break;
            }
        return res == -1 ? nums.size() : res;
    }
};

int main() {

    int nums[3] = {0, 1, 3};
    vector<int> vec(nums, nums + 3);
    cout << Solution().missingNumber(vec) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/missing-number/description/
/// Author : liuyubobobo
/// Time   : 2017-11-10

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

using namespace std;


/// HashSet
/// Time Complexity:  O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        unordered_set<int> records;
        for(int num: nums)
            records.insert(num);
        for(int i = 0 ; i <= nums.size() ; i ++)
            if(records.find(i) == records.end())
                return i;
        assert(false), "You should never reach here is the answer exist:)";
    }
};

int main() {

    int nums[3] = {0, 1, 3};
    vector<int> vec(nums, nums + 3);
    cout << Solution().missingNumber(vec) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/missing-number/description/
/// Author : liuyubobobo
/// Time   : 2017-11-10

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;


/// minus sum
/// Time Complexity:  O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        return n * (n+1) / 2 - accumulate(nums.begin(), nums.end(), 0);
    }
};

int main() {

    int nums[3] = {0, 1, 3};
    vector<int> vec(nums, nums + 3);
    cout << Solution().missingNumber(vec) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/missing-number/description/
/// Author : liuyubobobo
/// Time   : 2017-11-10

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;


/// Using XOR
/// Time Complexity:  O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res = 0;
        for(int i = 1 ; i <= nums.size() ; i ++)
            res ^= i;
        for(int num: nums)
            res ^= num;
        return res;
    }
};

int main() {

    int nums[3] = {0, 1, 3};
    vector<int> vec(nums, nums + 3);
    cout << Solution().missingNumber(vec) << endl;

    return 0;
}