Problem 1: An array n - 1 unique numbers in the range from 0 to n - 1. There is only one number in the range from 0 to n - 1 missing. Please write a function to find the missing number.
int getOnceNumber_unsorted(int* numbers, int length)
{
if(numbers == NULL || length <= 0)
return -1;
sum1 += numbers[i];
}
Problem 2: An sorted array n - 1 unique numbers in the range from 0 to n - 1. There is only one number in the range from 0 to n - 1 missing. Please write a function to find the missing number.
Since numbers from 0 to n - 1 are sorted in an array, the first numbers should be same as their indexes. That's to say, the number 0 is located at the cell with index 0, the number 1 is located at the cell with index 1, and so on. If the missing number is denoted as m. Numbers less then m are located at cells with indexes same as values.
The number m + 1 is located at a cell with index m, The number m + 2 is located at a cell with index m + 1, and so on. We can see that, the missing number m is the first cell whose value is not identical to its value.
if(numbers == NULL || length <= 0)
return -1;
while(left <= right)
{
int middle = (right + left) >> 1;
if(numbers[middle] != middle)
{
if(middle == 0 || numbers[middle - 1] == middle - 1)
return middle;
right = middle - 1;
}
else
left = middle + 1;
}
if(left == length ) // corrected by Kyunghee Kim
return length;
Read full article from Coding Interview Questions: No. 37 - Missing Number in an Array
int getOnceNumber_unsorted(int* numbers, int length)
{
if(numbers == NULL || length <= 0)
return -1;
int sum1 = 0;
for(int i = 0; i < length; ++i)sum1 += numbers[i];
int sum2 = length * (length + 1) / 2;
return sum2 - sum1;}
Problem 2: An sorted array n - 1 unique numbers in the range from 0 to n - 1. There is only one number in the range from 0 to n - 1 missing. Please write a function to find the missing number.
Since numbers from 0 to n - 1 are sorted in an array, the first numbers should be same as their indexes. That's to say, the number 0 is located at the cell with index 0, the number 1 is located at the cell with index 1, and so on. If the missing number is denoted as m. Numbers less then m are located at cells with indexes same as values.
The number m + 1 is located at a cell with index m, The number m + 2 is located at a cell with index m + 1, and so on. We can see that, the missing number m is the first cell whose value is not identical to its value.
int getOnceNumber_sorted(int* numbers, int length)
{if(numbers == NULL || length <= 0)
return -1;
int left = 0;
int right = length - 1;while(left <= right)
{
int middle = (right + left) >> 1;
if(numbers[middle] != middle)
{
if(middle == 0 || numbers[middle - 1] == middle - 1)
return middle;
right = middle - 1;
}
else
left = middle + 1;
}
if(left == length ) // corrected by Kyunghee Kim
return length;
return -1;
}Read full article from Coding Interview Questions: No. 37 - Missing Number in an Array
