Amazon Interview Question
Software EngineersTeam: Seattle
Country: United States
Interview Type: Phone Interview
Modified binary search is definitely the way to go. If numbers are in sequence, then the difference between two array values should equal the difference of their indices. If not, then the missing number is somewhere in that range.
public static int findMissingNumber(int[] a) {
// Validate... Assume -1 is fine to return for not found.
if (a == null || a.length == 0) {
System.out.println("Invalid sequence: length.");
return -1;
}
int low = 0;
int mid;
int high = a.length-1;
while (low < high) {
mid = low + (high - low) / 2;
if (a[mid] - a[low] == mid - low) {
// Missing number is in upper half
if (mid + 1 < a.length && a[mid + 1] != a[mid] + 1) {
return a[mid] + 1;
} else {
low = mid + 1;
}
} else {
// Missing number is in lower half
if (mid - 1 >= 0 && a[mid] - 1 != a[mid - 1]) {
return a[mid] - 1;
} else {
high = mid -1;
}
}
}
System.out.println("Invalid sequence: not found.");
return -1;
}
Best case: O(1) Average case: O(log n) Worst case: O(log n)
@Ragesh
how do you propose to find the sum of all the numbers present in the array without traversing the array at least once? for finding the sum O(n) is the best you can do.
Since you haven't mentioned what the sequence is i am assuming it to be an Arithmetic progression .
Lets assume the sequence is of the form of an arithmetic progression so according to the formula
a(n) = first_term +(n-1)common_difference
while iterating over the array check that for every iteration the next number fits the above equation
lets say at kth element the above equation is not satisfied break your loop & print a(k).
complexity O(k+k) ~ O(k)
worst case complexity O(n)
If the numbers are Sorted we can use a modification of the Binary Search to look for the missing number this will give us a O(logN) time complexity, the idea is to compare the value in the array with the index to determinate witch part of the array is going to be discarded.
public static int FindMissingInSequence(int[] a)
{
int missing = 0;
int start = 0;
int end = a.Length - 1;
while (start < end)
{
int midle = (start + end) / 2;
if (midle + 1 == a[midle])
start = midle + 1;
else
end = midle - 1;
}
if (start > end)
return -1;
return (start + 1 == a[start]) ? a[start] + 1 : a[start] - 1;
}
In the case that the sequence doesn't start from 1 a small modification is required.
For the other discussion, to sum the values, an alternative is to use XOR operation, this way is preferred because in the case of a big array with big numbers an overflow can be reached. In this algorithm we have O(N) time complexity so the binary approach is preferred.
public static int FindMissingInSequence(int[] a)
{
int missing = 0;
for (int i=0; i < a.Length; i++)
{
missing = missing ^ a[i];
}
for (int i=1; i <= a.Length + 1; i++)
{
missing = missing ^ i;
}
return missing;
}
If the numbers are sorted:
public class MissingNumber {
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[] = {22, 23 ,24 , 25 , 26 , 27 , 28 , 29 , 31 , 32 , 33 , 34};
System.out.println(binarySearch ( arr , 0 , arr.length - 1 , arr.length - 1));
}
private static int binarySearch(int[] arr , int start , int end , int lastIndex) {
// TODO Auto-generated method stub
if ( start > end)
return -1;
int mid = ( start + end ) / 2;
if ( mid-1 >=0 && arr[mid]-1 != arr[mid-1] ) {
return arr[mid] - 1;
}
else if ( mid+1 <= lastIndex && arr[mid+1] != arr[mid] + 1) {
return arr[mid]+1;
}
else {
if ( arr[mid] - arr[0] == mid - 0) {
return binarySearch(arr , mid+1, end, lastIndex);
}
else {
return binarySearch ( arr , start , mid - 1 , lastIndex);
}
}
}
}
Binary Search.
Any number at index 'r' can be represented as a+r*d (a is starting number, d is diff)
if the number at 'mid' does not match the expectation, then the missed number already happened, so look in left half of the array, else look in right half of array.
Also, to calculate diff, we need to make sure that diff between a[i] and a[i+1] and a[i+1] and a[1+2] is same (as it might be missed number already happened).
Time complexity: O(log(n))
If the sequence is 1, 2, 3, ... , n (order is not required) and only one number is missed, we can just sum all numbers and missed number is equal (n*(n-1)/2 - sum)
- Mike L September 02, 2016