**: An array**

__Problem 1__*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.

**If we scan all numbers in the array, we could get the sum of all numbers. The sum is denoted as**

__Analysis:__*sum1*.

Additionally, we could also get the sum of all numbers in the range from 0 to

*n*- 1, which is

*n**(

*n*-1)/2. The sum is denoted as

*sum2*.

The only number missing in the array is the difference between

*sum2*and

*sum1*.

This solution can be implemented with the following code:

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;}

Since we have to scan all numbers in the array, it costs O(

*n*) time if the size of array is

*n*.

**: An**

__Problem 2__**array**

*sorted**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.

**Of couse, we could use the solution above to solve this problem, which costs O(**

__Analysis:__*n*) time. This solution does not utilize the properties of sorted arrays.

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.

Therefore, it is required to search in an array to find the first cell whose value is not identical to its value. Since the array is sorted, we could find it in O(lg

*n*) time based on the binary search algorithm as implemented below:

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;

}The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.

This comment has been removed by the author.

ReplyDeleteThis works if the items in the array starts from 0 to n ,what if the items starts from n to m in the array then here is a solution:

ReplyDeleteAssumption : array sorted ascending

int findMissingNumber(int [] a)

{

int startIndex=0;

int endIndex =a.length-1;

int midIndex =(startIndex+endIndex)>>1;

while( startIndex < endIndex ){

if( a[midIndex] -a[startIndex] !=midIndex-startIndex)

{

if( midIndex -startIndex ==1 && a[midIndex] -a[startIndex] >1)

{

return midIndex-1;

}

endIndex =midIndex;

midIndex= (startIndex+endIndex)>>1

}

else if( a[endIndex] -a[midIndex] !=endIndex-midIndex){

if( endIndex -midIndex ==1 && a[endIndex] -a[midIndex] >1)

{

return midIndex+1;

}

startIndex =midIndex;

midIndex= (startIndex+endIndex)>>1

}

// Not found

return -1;

}

}

Hi, how about this problem?

ReplyDelete1~n unique numbers, but been written as string and all numbers are head-tail linked, in random order, find out the missing number.

For example, input: 1 to 13, 12 numbers, been written as "2113871101269"

The sum will not work. buy I think it could be solved by dynamic programming?

u can solve it from the last by using %10 in every loop and check in every loop whether the next digit is 1 if 1 take it as 2 digit or as one digit only for 3 times bcoz of(0 to 13 )values

Deleteand also check whether the ones number is 1 to 3

DeleteHi Harry, in the solution for the problem 1, should the sum2 be length*(length-1)/2, i.e., n*(n-1)/2? Because the smallest number in the array is 0 not 1.

ReplyDeleteThe code is correct, because the length of the array is n-1, rather than n. One number in the range from 0 to n-1 is missing.

DeleteGreat thanks to Kyunghee Kim, who helped to correct an issue when the missing number is the greatest number in the sorted array. The post has been updated with the fix.

ReplyDeleteIt should be

Deleteif(left == length-1 )

return (length-1);

int getOnceNumber_unsortedXOR(int* numbers, int length)

ReplyDelete{

if(numbers == NULL || length <= 0)

return -1;

int i = 0, result = 0;

do result ^= numbers[i]^i++;

while( i < length );

return result^i;

}

class Solution {

ReplyDeletepublic:

int missingNumber(vector& nums) {

int r = 0;

for (int i = 0; i<nums.size(); i++){

r ^= i ^ nums[i];

}

return r ^ nums.size();

}

};

URL: http://traceformula.blogspot.com/2015/09/missing-number-leetcode.html