Last Updated on March 30, 2022 by Ria Pathak
CONCEPTS USED:
Binary Search
DIFFICULTY LEVEL:
Medium
PROBLEM STATEMENT(SIMPLIFIED):
Given an array
A, such that it is arranged in anArithmetic 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 Searchwould be an efficient alternative here.
OBSERVATION:
Every element in an A.P. can be calculated using its position i.e.
arr[i] = arr[0] + 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 –
The idea is to use
Binary Search.We initialize
lowandhighas0andn-1, and calculatemidas
mid = low + (high - low)/2If the element present at
midmatches the calculated value atmid, this implies that elements at the lower half are all positioned correctly, so we search in the right half.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 ourresult`.
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[0] + 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[0] + mid*diff;
return MissingAP(arr, low, mid - 1, diff, missing_ele);
}
}
//finally return the ele that was not found on its place
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[1] - arr[0];
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[0] + 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[0] + 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[0] + mid*diff;
return MissingAP(arr, low, mid - 1, diff, missing_ele);
}
}
//finally return the ele that was not found on its place
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[1] - arr[0];
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[0] + 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[0] + 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[0] + mid*diff;
return MissingAP(arr, low, mid - 1, diff, missing_ele);
}
}
//finally return the ele that was not found on its place
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[1] - arr[0];
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[0] + 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.