New update is available. Click here to update.

Binary Search Notes

Binary Search on Matrix

0% completed

Search in Rotated Sorted Array

Search in a 2-D Matrix

Search in a 2-D Matrix II

First and Last Position of an element in sorted array

Occurrence of x in a sorted array

Binary Search on Answer

0% completed

Allocate Books

Recycling Pens

Square root of an Integer

Aggressive Cows

Painter's Partition Problem

Mixed Problems related to Binary Search

0% completed

Chess Tournament

Ninja and Candies

Minimum time to Solve the Problems

Square Submatrix with Sum less than or equal to K

Smart Intervals

Distribute N candies among K people

Search in Infinite Sorted array of 0 and 1

Find pair Sum in rotated sorted Array

Find peak element

Find Missing Number in AP

Find Best Insertion Position in Array

Problem

Submissions

Solution

New

Discuss

Missing number in Arithmetic progression

Last Updated: 23 Feb, 2023

Easy

0/40

Avg time to solve 15 mins

Success Rate 85 %

29 upvotes

Problem Statement

Suggest Edit

You are given a sorted array of ‘N’ distinct integers that are in the Arithmetic Progression sequence except for one element which is missing from the sequence. You have to find that missing number from the given sequence.

Note:

1. A sequence [arr0, arr1,…, arr(n-1)] is called an Arithmetic progression if for each 'i' ( 0 ≤ i < n - 1) the value arr[i+1] − arr[i] is the same. 
2. There is exactly one missing number in the given sequence.
3. All the numbers present in the sequence are distinct.
4. It is the guarantee that the first and last elements of the sequence are not missing elements.

Follow Up

The overall run time complexity should be O(log(N)).

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single positive integer ‘N’ denoting the number of the elements present in the sequence. 

The second line of each test case contains ‘N’ space-separated integers.

Output Format:

The only line of output of each test case should contain an integer denoting the missing element in the given sequence.

Print the output of each test case in a separate line.

Constraints:

1 <= T <= 50
3 <= N <= 10 ^ 4   
-10 ^ 9 <= Arr[i] <= 10 ^ 9 

Where ‘T’ is the number of test cases, ‘N’ is the size of the array and ‘Arr[i]’ is the size of the array elements.

Time Limit: 1 sec

Sample Input 1:

Sample Output 1:

 7
 15

Explanation for sample input 1:

Test case 1:

The arithmetic sequence present in the first test case will have its first term as 4 and common difference as 3. So, the complete sequence will look like this ....- 1 4 7 10... Hence 7 is the missing element in the given sequence.

Test case 2:

The first term and common difference will be 5. The complete sequence will be ...5 10 15 20 25.... Hence 15 is the missing element from the given sequence.

Sample Input 2:

3
3
-1 0 2
5 
10 20 30 50 60
4
12 18 21 24

Sample Output 2:

1
40
15

Auto

Console