268. Missing Number

so the clearest way maybe using an array of boolean and give a check in the bool array as we scan through the numbers given. then we scan the boolean array to find out the missing one. with time O(N)

also we can sort the array first, then scan the list to see the missing one. that would be O(NlogN). without using extra space.

then of course we can think of adding up the numbers all together, and use (1 + n)*n/2 to minus the summary of the numbers giving and then we can find out the missing one. but it could overflow, as the sum may become very big with a big n. anyhow the time becomes O(N).

but the best way maybe using a^a = 0 and a^b^c = a^(b^c). we can need an integer to get the xor of all the giving numbers. and use this interger to xor(1..n). then we can findout the missing number.

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