Thinking Process I

since the numbers should be from [0 .... n] and one number is missing. Then the sum of input should the total sum of [0 ... n] minus the given input sum.

public class Solution {
    public int missingNumber(int[] nums) {
        int sum = 0;
        int count = 0;
        for (int i = 0; i < nums.length; ++i) {
            sum += nums[i];
            count += i + 1;
        }

        return count - sum;
    }
}

Thinking process II

since we know that x ^ y ^ y = x, and if the there's no missing number, then the index and value should be perfectly matched.

• nums[0] = 0, nums[1] = 1
• even if it is not in order, same value should appear twice instead of one, similar to the question of single number

public class Solution {
    public int missingNumber(int[] nums) {
        int res = nums.length;
        for (int i = 0; i < nums.length; ++i) {
            res = res ^ i ^ nums[i];
        }

        return res;
    }
}