LeetCode 268. Missing Number

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ans = nums.size(), i = 0;
        for (const int num : nums)
            ans ^= i++ ^ num;
        return ans;
    }
};
1
2
3
4
5
6
7
8
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int expectedSum = nums.size() * (nums.size() + 1) / 2;
        int actualSum = accumulate(nums.begin(), nums.end(), 0);
        return expectedSum - actualSum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        // reference: https://leetcode.com/problems/couples-holding-hands/discuss/113362/JavaC%2B%2B-O(N)-solution-using-cyclic-swapping
        const int n = nums.size();
        for (int i = 0; i < n; ++i)
            for (int j = nums[i]; i != j && j != n; j = nums[i])
                swap(nums[i], nums[j]);
        for (int i = 0; i < n; ++i)
            if (nums[i] != i)
                return i;
        return n;
    }
};