An arithmetic array is one whose elements form an arithmetic sequence, in order

Question

An arithmetic array is one whose elements form an arithmetic sequence, in order - i.e., they're arrays of the form A = [a_1, a_1 + c, a_1 + 2c, ..., a_1 + (n - 1)c], where A has length n (for n Greaterthanorequalto 2). You're given an arithmetic array with one element missing from somewhere in the middle (i.e., it's not the first or last element that's been removed). For example, the missing number in [3, 6, 12, 15, 18] is 9. The missing number in [1, 15, 22, 29, 36] is 8. Describe a way to calculate c in constant time. Design an algorithm to efficiently find the missing number in the array. Briefly justify a good asymptotic runtime of your algorithm.

Explanation / Answer

We can solve this problem in O(Logn) time using Binary Search. The idea is to go to the middle element.
Check if the difference between middle and next to middle is equal to diff or not,
if not then the missing element lies between mid and mid+1.
If the middle element is equal to n/2th term in Arithmetic Series (Let n be the number of elements in input array),
then missing element lies in right half.
Else element lies in left half.

Implementation:

Calculating c => c = (arr[n-1] - arr[0])/n;

int findMissing(int arr[], int low, int high, int diff)
{

if (high <= low)
return INT_MAX;
  
// Find index of middle element
int mid = low + (high - low)/2;
  
if (arr[mid+1] - arr[mid] != diff)
return (arr[mid] + diff);
  
// The element just before mid is missing
if (mid > 0 && arr[mid] - arr[mid-1] != diff)
return (arr[mid-1] + diff);
  
if (arr[mid] == arr[0] + mid*diff)
return findMissingUtil(arr, mid+1, high, diff);
  
return findMissingUtil(arr, low, mid-1, diff);
}
  

int findMissingTerm(int arr[], int n)
{

int diff = (arr[n-1] - arr[0])/n;
  
return findMissing(arr, 0, n-1, diff);
}

Since, we are ignoring half of the sequence in each recurson, so we have:

T(n) = T(n/2) + O(1) => O(logn)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.