# 268. Missing Number (Easy)

https://leetcode.com/problems/missing-number/

Given an array containing n distinct numbers taken from `0, 1, 2, ..., n`, find the one that is missing from the array.

Example 1:

```Input: [3,0,1]
Output: 2
```

Example 2:

```Input: [9,6,4,2,3,5,7,0,1]
Output: 8
```

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

## Solutions

``````class Solution {
public int missingNumber(int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}

int n = nums.length;

// n is the special case, check out whether it exists or not.
boolean nExists = false;
for (int i = 0; i < n; i++) {
if (nums[i] == n) {
nExists = true;
break;
}
}

// If not present, return it immediately.
if (!nExists) {
return n;
}

for (int i = 0; i < n; i++) {
if (nums[i] == n) {
continue;
}

if (nums[i] != i) {
// swap nums[i] to its corresponding slot
swap(nums, nums[i], i);

// do not move forward until current position is settled
i--;
}
}

// Finally, the slot of missing number will be swapped in n
for (int i = 0; i < n; i++) {
if (nums[i] != i) {
return i;
}
}

return -1;
}

private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
``````