268.md

268. 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.

For example, Given nums = [0, 1, 3] return 2

Thinking Process

1. Note that the range of the number in the array is from 0 - n, while the length of the array is n - 1
2. The elements of the array are indexed from 0 - (n-1)
3. XOR every element of the array, and XOR numbers from 0 - n.
4. Non-missing element will XOR with its equivalent index to 0, the remainder of the result is the missing number

public int missingNumber(int[] nums) {
	int missing = 0;
    for(int i=0; i<nums.length + 1; i++){
        missing ^= i;
        if(i == nums.length)
            continue;
        else
            missing ^= nums[i];
    }
    return missing;
}

Complexity

1. The array is scanned once, time complexity is O(n)
2. No extra storage is required, space complexity is O(1)