Missing in AP

CONCEPTS USED:

Binary Search

DIFFICULTY LEVEL:

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[0] + i*diff

SOLVING APPROACH:

First check for corner cases :
> First refer best online learning sites for programming to 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[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--;
    }
  }
}

Space Complexity: O(1)

Previous post Balancing the Magnets
Next post Zigzag String

Leave a Reply

Your email address will not be published. Required fields are marked *