Missing Number

Description

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note: Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Solutions

My solution

Idea: if nums[i] > 0, mark its existence by subtracting n + 1 from nums[nums[i] - 1] (so it is < 0). Use a separate variable to mark the existence of 0.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        bool zero = false;
        for(int num : nums){
            int val = num < 0 ? num + n + 1 : num;
            if(val == 0)
                zero = true;
            else{
                int idx = val - 1;
                nums[idx] -= (n + 1);
            }
        }
        if(!zero) return 0;
        int i;
        for(i = 0; i < n; ++i){
            if(nums[i] >= 0)
                break;
        }
        return i + 1;
    }
};

Optimal solution

Idea: use XOR. Becausea XOR a XOR b == b.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int ans = n;
        for(int i = 0; i < n; ++i){
            ans ^= i;
            ans ^= nums[i];
        }
        return ans;
    }
};