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.
Analysis: If we scan all numbers in the array, we could get the sum of all numbers. The sum is denoted as 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;
sum1 += numbers[i];
}
Since we have to scan all numbers in the array, it costs O(n) time if the size of array is n.
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.
Analysis: Of couse, we could use the solution above to solve this problem, which costs O(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(lgn) time based on the binary search algorithm as implemented below:
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;
More coding interview questions are discussed in my
book <Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.
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.
Analysis: If we scan all numbers in the array, we could get the sum of all numbers. The sum is denoted as 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.
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.
Analysis: Of couse, we could use the solution above to solve this problem, which costs O(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(lgn) 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
NayHoh,
ReplyDeleteThe sense of praise that I have found for you after reading No. 37 - Missing Number in an Array is overwhelming! Such a tremendous read!
I know that recently Amazon introduced a 25 domains limit for encrypted domains on a single Load Balancer. AWS Tutorial I think many developers are in the same situation as my, if you have 1000 domains it's not practical to create and manage 40 load balancers.
Appreciate your effort for making such useful blogs and helping the community.
Grazie,
Irene Hynes
Bonjour,
ReplyDeleteI genuinely do look forward for the time where you post some new write ups. Your blog make me feel so educated! Continue soaring and writing please.
is this the right place for this kind of request? i would like to know when we can expect CodeCommit to be available in Frankfurt region, also in general i would like to know if there is some place where i can see which service is planned to be deployed in which region etc. so we will know which service can we expect when and where.
AWS Training USA
Anyways great write up, your efforts are much appreciated.
Many Thanks,
Ajeeth
Hello Buddie,
ReplyDeleteThanks for highlighting this and indicating about No. 37 - Missing Number in an Array where more study and thought is necessary.
I would like to post an announcement for anyone who needs server resources at AWS. Basically, I have 600$ worth of AWS Credit and I am looking for people who would like to use these credits since I don't need them. The only issue here is that they expire at April 30th. I am ready to negotiate and maybe exchange for 150$ amazon gift card or something more tangible for me. Also, I am open to any kind of negotiation. AWS Training
Awesome! Thanks for putting this all in one place. Very useful!
Obrigado,
Ajeeth
Ni Hau,
ReplyDeleteSeems like I won the lottery here….This is a treasure box of blogs and your folks are like leprechauns! Phenomenal read on No. 37 - Missing Number in an Array !
If AWS Certification says that I need to recertify by a specific date, is that date the final day that I can possibly take the recertification (or corresponding professional-level) exam? AWS Training USA
Once again thanks for your tutorial.
Obrigado,
Radhey