  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Missing in AP

Last Updated on March 30, 2022 by Ria Pathak Binary Search

Medium

### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given an array `A`, such that it is arranged in an `Arithmetic Progression`, but one element from this A.P. is missing, find it.

See original problem statement here

#### For Example:

``````Input : A = [3, 6, 12, 15, 18]

Output : 9

Explanation : 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.``````

Can we use `Binary Search` here ?

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` would be an efficient alternative here.

### OBSERVATION:

Every element in an A.P. can be calculated using its position i.e.
`arr[i] = arr + i*diff`

### SOLVING APPROACH:

First check for corner cases :

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.
Else we will follow below approach –

1. The idea is to use `Binary Search`.

2. We initialize `low` and `high` as `0` and `n-1`, and calculate `mid` as
`mid = low + (high - low)/2`

3. If the element present at `mid` matches the calculated value at `mid`, this implies that elements at the lower half are all positioned correctly, so we search in the right half.

4. else we store the calculated value and search in the lower half till
`low 6. In this way, we will have the last value that was not at its right position stored with us which will be our `result`.

### SOLUTIONS:

```
#include <stdio.h>

#include <stdio.h>

int MissingAP(int *arr, int low, int high, int diff, int missing_ele){
if(low <= high){
int mid = low + (high - low)/2;

/* if curr element is at its right place in AP
we will search in the lower half then */
if(arr[mid] == arr + mid*diff)
return MissingAP(arr, mid+1, high, diff, missing_ele);

/* else save the value that should be here and further
search in the lower half */
else{
missing_ele = arr + mid*diff;
return MissingAP(arr, low, mid - 1, diff, missing_ele);
}
}
return missing_ele;
}

int main()
{
int t; scanf("%d", &t);
while(t--){
int n; scanf("%d", &n);
int arr[n];
for(int i=0; i<n; i++)
scanf("%d", &arr[i]);

//check if missing element lies at one of the ends or close to one of the ends
int left_diff = arr - arr;
int right_diff = arr[n-1] - arr[n-2];
int diff, missing_ele;

//if left == right, missing element lies inside of the array
if(left_diff == right_diff){
diff = left_diff;
//we will go on checking inside the array
printf("%d\n", MissingAP(arr, 0, n-1, diff, -1));
continue;
}

//else missing ele is at one of the corners or near corner
if(left_diff < right_diff){
missing_ele = arr[n-1] - left_diff;
printf("%d\n", missing_ele);
}
else{
missing_ele = arr + right_diff;
printf("%d\n", missing_ele);
}
}
return 0;
}
```
```
#include <bits/stdc++.h>
using namespace std;

int MissingAP(int *arr, int low, int high, int diff, int missing_ele){
if(low <= high){
int mid = low + (high - low)/2;

/* if curr element is at its right place in AP
we will search in the lower half then */
if(arr[mid] == arr + mid*diff)
return MissingAP(arr, mid+1, high, diff, missing_ele);

/* else save the value that should be here and further
search in the lower half */
else{
missing_ele = arr + mid*diff;
return MissingAP(arr, low, mid - 1, diff, missing_ele);
}
}
return missing_ele;
}

int main()
{
int t; cin>>t;
while(t--){
int n; cin>>n;
int arr[n];
for(int i=0; i<n; i++)
cin>>arr[i];

//check if missing element lies at one of the ends or close to one of the ends
int left_diff = arr - arr;
int right_diff = arr[n-1] - arr[n-2];
int diff, missing_ele;

//if left == right, missing element lies inside of the array
if(left_diff == right_diff){
diff = left_diff;
//we will go on checking inside the array
cout<<MissingAP(arr, 0, n-1, diff, -1)<<"\n";
continue;
}

//else missing ele is at one of the corners or near corner
if(left_diff < right_diff){
missing_ele = arr[n-1] - left_diff;
cout<<missing_ele<<"\n";
}
else{
missing_ele = arr + right_diff;
cout<<missing_ele<<"\n";
}
}
return 0;
}
```
```
import java.util.*;
import java.io.*;

public class Main {
static int MissingAP(int []arr, int low, int high, int diff, int missing_ele){
if(low <= high){
int mid = low + (high - low)/2;

/* if curr element is at its right place in AP
we will search in the lower half then */
if(arr[mid] == (arr + mid*diff))
return MissingAP(arr, mid+1, high, diff, missing_ele);

/* else save the value that should be here and further
search in the lower half */
else{
missing_ele = arr + mid*diff;
return MissingAP(arr, low, mid - 1, diff, missing_ele);
}
}
return missing_ele;
}

public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t != 0){
int n = sc.nextInt();
int arr[] = new int[n];
for(int i=0; i<n; i++)
arr[i] = sc.nextInt();

//check if missing element lies at one of the ends or close to one of the ends
int left_diff = arr - arr;
int right_diff = arr[n-1] - arr[n-2];
int diff, missing_ele;

//if left == right, missing element lies inside of the array
if(left_diff == right_diff){
diff = left_diff;
//we will go on checking inside the array
System.out.println(MissingAP(arr, 0, n-1, diff, -1));
t--;
continue;
}

//else missing ele is at one of the corners or near corner
if(left_diff < right_diff){
missing_ele = arr[n-1] - left_diff;
System.out.println(missing_ele);
}
else{
missing_ele = arr + right_diff;
System.out.println(missing_ele);
}
t--;
}
}
}
```

[forminator_quiz id="1534"]
Space Complexity: O(1)

This article tried to discuss the concept of Binary Search. Hope this blog helps you understand and solve the problem. To practice more problems on Searching you can check out MYCODE | Competitive Programming.