# Find the Missing Number

## Question

### Problem Statement

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.

## 题解1 - 位运算

### Java

public class Solution {
/**
* @param nums: an array of integers
* @return: an integer
*/
public int findMissing(int[] nums) {
if (nums == null || nums.length == 0) return -1;

// get xor from 0 to N excluding missing number
int x1 = 0;
for (int i : nums) {
x1 ^= i;
}

// get xor from 0 to N
int x2 = 0;
for (int i = 0; i <= nums.length; i++) {
x2 ^= i;
}

// missing = x1 ^ x2;
return x1 ^ x2;
}
}


## 题解2 - 桶排序

### Java

public class Solution {
/**
* @param nums: an array of integers
* @return: an integer
*/
public int findMissing(int[] nums) {
if (nums == null || nums.length == 0) return -1;

bucketSort(nums);
// find missing number
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i) {
return i;
}
}

return nums.length;
}

private void bucketSort(int[] nums) {
for (int i = 0; i < nums.length; i++) {
while (nums[i] != i) {
// ignore nums[i] == nums.length
if (nums[i] == nums.length) {
break;
}
int nextNum = nums[nums[i]];
nums[nums[i]] = nums[i];
nums[i] = nextNum;
}
}
}
}


### 源码分析

1. N 不在原数组中，故最后应该返回 N
2. N 在原数组中，但不在数组中的最后一个元素
3. N 在原数组中且在数组最后一个元素