Question

In this problem your task is to find a missing number. The input will always consist of an array of n positive integers such that the difference between every two consecutive numbers is a fixed constant but one integer is missing. See below for two example inputs/outputs: Input sequence: [0, 2, 4, 6, 10] Output: missing number is 8 Input sequence: [1, 4, 7, 13, 16] Output: missing number is 10 Note that in the first example the constant c is equal to 2 and in the second example the constant is equal to 3. You do not know before hand what the constant is. All you know is that c is just some positive integer.

1. Give an O(1)-time function to compute the constant c from any input list or array L

. 2. Give an O(n)-time algorithm to find the missing number (use the function from part (1)). Give pseudo-code and a short description.

3. Give an O(log n)-time divide-and-conquer algorithm to find the missing number (you also should use the function from part (1)). Give pseudo-code and a short description. Then give the recurrence relation and show that is solves to O(log n).

Answer 1

1. Find constant c in O(1) time

Approach : We cannot simply find difference between first 2 numbers. Because there can be scenario where 2 number is the missing number example [0,4,6,8,10], Hence we can find two difference and minimum of them is constant value.
int findConstant(Arr[1....N]):
a = Arr[2] - Arr[1]
b = Arr[3] - Arr[2]
c = min(a,b)
return c

2. Find missing number in O(n) time

Approach : We can simply traverse the array and check if next number have difference = c, if not then it is the missing number

int findMissingNumber(Arr[1...N]):
c = findConstant(Arr)
for i=1 to N-1:
if(Arr[i+1] != Arr[i]+c)
return Arr[i]+c

3. Divide and conquer approach to find missing number in O(logN) time

Approch : We can break array in two parts and decide which part to traverse based on whether missing number exists in left/right subarray. At the end size of array reduces to size of 2 where missing number lies between those two numbers

findMissingNumber(Arr[low...high], C):
start = Arr[low]
if(low+1 == high)
return start + C;
mid = low + (high - low)/2  
number = start + (mid-low) * C
if(Arr[mid] > number)
  return findMissingNumber(Arr[low...mid], C) // traverse to left subarray
else
return findMissingNumber(Arr[mid...high], C) // traverse to right subarray