Problem

Given an array contains N numbers of 0 .. N, find which number doesn't exist in the array.

Example

Given N = 3 and the array [0, 1, 3], return 2.

Challenge

Do it in-place with O(1) extra memory and O(n) time.

Solution

Muggle: O(nlogn)

public class Solution {
    public int findMissing(int[] nums) {
        // write your code here
        Arrays.sort(nums);
        int temp = nums.length; //这里做对最末位的比较
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                temp = i;
                break;
            }
        }
        return temp;
    }
}

Bit Manipulation

public class Solution {
    public int findMissing(int[] nums) {
        // write your code here
        int x = 0;
        for (int i = 0; i < nums.length; i++) {
            x ^= nums[i];
        }
        for (int i = 0; i <= nums.length; i++) {
            x ^= i;
        }
        return x;
    }
}