{"id":1514,"date":"2020-07-01T09:31:32","date_gmt":"2020-07-01T09:31:32","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1514"},"modified":"2022-03-30T13:21:28","modified_gmt":"2022-03-30T13:21:28","slug":"missing-in-ap","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/missing-in-ap\/","title":{"rendered":"Missing in AP"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Binary Search<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Medium<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Given an array A<\/code>, such that it is arranged in an Arithmetic Progression<\/code>, but one element from this A.P. is missing, find it.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example:<\/h4>\n
Input : A = [3, 6, 12, 15, 18]\n\nOutput : 9\n\nExplanation : In the given A.P. series starting with initial element 3 and Common Difference 3, 9 is the element that is missing between 6 and 12.<\/code><\/pre>\n
Can we use Binary Search<\/code> here ?<\/em><\/strong>  <\/p>\n
\n
Given that the array forms an A.P. this implies that it is either sorted in ascending or descending order and we need to search a missing number in it. Binary Search<\/code> would be an efficient alternative here.<\/p>\n<\/blockquote>\n
OBSERVATION:<\/h3>\n
\n
Every element in an A.P. can be calculated using its position i.e.
\narr[i] = arr[0] + i*diff<\/code><\/p>\n<\/blockquote>\n
SOLVING APPROACH:<\/h3>\n
First check for corner cases :<\/em><\/strong>  <\/p>\n
\n
First check whether the missing element lies near one of the corner points by taking out difference of first and second elements and difference of last and second last elements and comparing these differences with each other. If they are not equal, this implies that the missing number lies near corner points and we can easily compute the missing number.
\nElse we will follow below approach – <\/p>\n
    \n
  1. \n
    The idea is to use Binary Search<\/code>.  <\/p>\n<\/li>\n
  2. \n
    We initialize low<\/code> and high<\/code> as 0<\/code> and n-1<\/code>, and calculate mid<\/code> as
    \nmid = low + (high - low)\/2<\/code><\/p>\n<\/li>\n
  3. \n
    If the element present at mid<\/code> matches the calculated value at mid<\/code>, this implies that elements at the lower half are all positioned correctly, so we search in the right half.<\/p>\n<\/li>\n
  4. \n
    else we store the calculated value and search in the lower half till
    \nlow 6. In this way, we will have the last value that was not at its right position stored with us which will be our <\/code>result`.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
    SOLUTIONS:<\/h3>\n
    \t\t\t\t\t\t