Yahoo Interview Question
Software Engineer / Developersbinary search for what :)
Sum of numbers in a range can be calculated using n(n+1)/2 and thus find the missing number by summing the given numbers and calculating the difference.
I think we can safely assume there is no logN solution for this problem in its current form.
I think that too. All numbers between m and n except one must be inside the array. Otherwise, lots of numbers aren't in the array.
wonder y we cant do a binary search.. :-?
its sorted, we know the range, so we know the middle element, we know what it shud sum up to.. if the calculatedVlaue > anticipatedValue then missing number is within the first half.. and continue ur search.. O(log n)..
now looking for criticism..
this is the binary search..
Lets assume range is [m,n] i.e. m and n is included in range
int diff = (n-m )/2
if (arr[diff] = m+diff ) then
//missing element is in lower half i.e. between [diff+1,n]
else
//missing element is in upper half i.e. between [m,diff-1]
Can you please explain for what number you are checking ..
10-70
and 54 is missing
diff is middle range = 30
arr[30] = 10 + 30 ?? whats the logic of checking this ??
Here it will go to lower half as arr[30] = 40 , and are u comparing i.e == or assigning by =
Please explain ..
According to what i think its really not possible to find a missing number in a list .. Binary search is to find the position and number is present or not when you know the exact number that is given. Also we should have a sorted list
** According to what i think its really not possible to find a missing number in a log N time in a list
Assume that the range of the numbers are given (Otherwise we cannot differentiate the missing element when it is the first or last element)
We can still do a binary search by comparing the difference between positions and values.
Suppose the array is {0,1,2,4,5,6,7,8,9,10}, 3 is missing.
The first round of binary search will have left = 0, right = 9, mid = 0+(9-0)/2=4
And the element of left pointer is 0, mid pointer is 5
Since 5 - 0 > mid - left = 4, we can know that the missing element is on the left.
int binary_search(int *a, int left, int right) {
if (left >= right - 1) { //Deal with the edge condition
if ((left > 0) && (a[left] > a[left - 1] + 1))
return (a[left] - 1);
else
return (a[left] + 1);
}
int mid = left + (right - left) / 2;
if (mid - left < a[mid] - a[left])
binary_search(a, left, mid);
else
binary_search(a, mid, right);
}
int main() {
int a[10] = {0,1,2,4,5,6,7,8,9,10};
cout << binary_search(a, 0, 9) << endl;
}
This solution will return '0' all the time...
The problem with is as follows:
if (mid - left < a[mid] - a[left])
binary_search(a, left, mid); <<<< You are not returning the value from stack
else
binary_search(a, mid, right); <<<< You are not returning the value from stack
The solution is as follows:
if (mid - left < a[mid] - a[left])
return (binary_search(a, left, mid));
else
return (binary_search(a, mid, right));
It can be done in o(logn) time. Simple binary search will do.
For each iteration, we can compare low,mid and high. if(mid-low) == (array[mid]-array[low]) it means all elements are present in first half(low to mid) and the missing element is present in the later half(mid to high). We can continue the binary search(recursive call) on the later half(mid to high).
This will take o(logn) as it is binary in approach.
Cant you just check if current array[index] = index then its fine up to now...
because if array is sorted and continuous and starting from 0 then for every element array[index] = index.
if its not starting from 0 but x then array[index] = index+x. It will be sorted and continuous...always...
To find the missing element in O(log n) you need to use binary search idea
Assumption : the array sorted in ascending order
public int findMissingElement ( int [] a ){
if( a.lenght<2)
return -1
int start =0;
int end =a.length;
int mid =(start +end)>>1;
while(start<end){
if ( a[mid] - a[start] != mid -start ){
if( mid - start == 1 && a[mid]-a[start]>1)
return a[mid]-1;
end =mid;
mid =(start+end)>>1;
}
else if ( a[end] - a[mid] != end -mid ){
if( end - mid == 1 && a[end] - a[mid] >1)
return a[mid] +1;
start =mid;
mid =(start+end)>>1;
}
// Everything ok
return -1;
public int findMissingElement(int start , int end , int a [] )
{
if (end < start)
return -1; // not found means Ok
else {
int mid = (start + end)>>1;
if( mid - start ==1 && a[mid] - a[start] >1)
reutn a[mid]-1;
if ( end - mid == 1 && a[end] - a[mid] >1)
return a[mid]+1;
if( a[mid] - a[start] != mid - start ){
return findMissingElement (start ,mid,a);
}
else ( a[end] - a[mid] != end - mid ){
return findMissingElement (mid ,end,a);
}
}
}
The question is a bit ambiguous:
1. Are the elements (val) continuously inc. by 1 meaning any element at index x is 1 less than element x + 1 ?
2. is the first element starting at 0 ?
So, I will try to provide my answer on the assumption that Yes for question (1) and (2) above.
Assume we have an array of 10 elements (or N elements of a general case). And, assume element 3 is missing (or any x where x >= 0 and x <= N-1;
Array index: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Array with missing: [0, 1, 2, 4, 5, 6, 7, 8, 9] // 3 is missing from the sorted array.
Algorithm:
1. If there are only 2 element, then the element which the index != Array[index] is the one missing.
2. else
a. find the mid point.
b. compare the index of array with the Array[index]
if (index < Array[index]) then the missing one is in the first (left) half of the array.
else the missing one is in the second (right) half of the array.
int missing(int A[], int begin, int end)
{
int mid = (begin + end)/2;
if (begin +1 == end)
return ((A[begin] != begin)? begin:end;
if (mid < A[mid])
return missing(A, begin, mid);
else
return missing(A, mid, end);
}
You can see that at each iteration, we are eliminating half of the array. Thus, it is an O(logn).
Any constructive comment ?
Ok this is if the numbers are in the increasing format with one value. what if the numbers are sorted in arithmetic progression but not the index is not equal to the value of that index.
for ex, what if we have this array{1,4,7,10,16,19,22,...} the missing number is 13. Does the binary search is working with this? I think it will work just withe special sorted array but not to find general missing value in the sorted array. In this case can we use binary search in o(long) time to find the answer of it?
Thanx
This can be solved in O(logn) using binary search .
int find_bs(int a[],int l,int n)
{
if(l==n)
{
if(a[l]-a[l-1]>1)
return a[l]-1;
else
return a[l]+1;
}
int mid=(n+l)/2;
if(a[mid]-a[0]==mid)
{
find_bs(a,mid+1,n);
}
else
{
find_bs(a,l,mid-1);
}
}
int main()
{
int arr[]={3,4,5,6,7,8,9,10,11,12,13,15};
cout<<find_bs(arr,0,11);
return 0;
}
#include<iostream>
using namespace std;
int find_bs(int a[],int l,int n)
{
if(l==n)
{
if(a[l]-a[l-1]>1)
return a[l]-1;
else
return a[l]+1;
}
int mid=(n+l)/2;
if(a[mid]-a[0]==mid)
{
find_bs(a,mid+1,n);
}
else
{
find_bs(a,l,mid-1);
}
}
int main()
{
int arr[]={3,4,5,6,7,8,9,10,11,12,13,15};
cout<<find_bs(arr,0,11);
return 0;
}
static int MissingNumber(int [] a, int n)
{
int low = 0, mid = 0, high = n-1;
while (low <= high)
{
mid = (low+high)/2;
if( mid == 0 || a[mid] - a[mid - 1] > 1 ) // order of logic must be preserved as shown.
return a[mid] - 1;
if (a[mid] - mid > 1)
high = mid - 1;
else //(a[mid] - mid == 1)
low = mid + 1;
}
return 0;
}
I think for this question one has to know the range of elements in sorted array.
- Anonymous September 12, 2010eg range of elements is ( m to n ). All elements exist in this range are there in array except one. now just do binary search as array is sorted.