# [leetcode] Missing Number

### Missing Number

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

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

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

4/10/2015 update

```class Solution {
public:
int missingNumber(vector<int>& nums) {
int i = 0;
while(i < nums.size()){
if(nums[i] == i || nums[i] == nums.size()){
i++;
}
else{
int tmp = nums[nums[i]];
nums[nums[i]] = nums[i];
nums[i] = tmp;
}
}
for(int i = 0; i < nums.size(); i++){
if(i != nums[i]){
return i;
}
}
return nums.size();
}
};```

The key to solve this problem is to put all the elements in right places. (make nums[i] = i). It’s just like a sort algorithm while runs in linear time. I set ‘tail’ variable to -1 to mark it as ’empty’.

```//So the size of the array must be n?
//What's the space and time complexity requirements?
//

class Solution {
public:
int missingNumber(vector<int>& nums) {
int tail = -1;
int i = 0;
while(i < nums.size()){
//element is in the right place
if(nums[i] == i){
i++;
}
else{
//element is not in the right place
if(nums[i] == nums.size()){
int tmp = tail;
tail = nums[i];
nums[i] = tmp;
}
//empty slot
else if(nums[i] == -1){
i++;
}
else{
//swap
int tmp = nums[i];
nums[i] = nums[nums[i]];
nums[tmp] = tmp;
}
}
}
//check for tail
if(tail != -1 && tail != nums.size()){
//swap tail and nums[tail]
int tmp = tail;
tail = nums[tmp];
nums[tmp] = tmp;
}
//n is missing
if(tail == -1) return nums.size();

for(int i = 0; i < nums.size(); i++){
if(nums[i] != i) return i;
}
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.