Find the missing number in Arithmetic Progression
Last Updated : 23 Jul, 2025
Given an array arr[] that represents elements of arithmetic progression in order. One element is missing in the progression, find the missing number.
Note: An element will always exist that, upon inserting into a sequence forms Arithmetic progression. If the given sequence already forms a valid complete AP, return the (n+1)th element that would come next in the sequence.
Examples:
Input: arr[] = [2, 4, 8, 10, 12, 14]
Output: 6
Explanation: In this case, the common difference is 2, and 6 is missing between 4 and 8.
Input: arr[] = [1, 6, 11, 16, 21, 31]
Output: 26
Explanation: In this case, the common difference is 5, and 26 is missing between 21 and 31.
A simple Solution is to linearly traverse the array and find the missing number. We know that in an AP,
Sum of the n elements (s) = ((n+1)/2) * (a + (a +diff*n))
n is the number of elements, a is the first element and diff is difference between the each term of the AP. (a + diff*n) is the (n+1)th element of the AP.
If we take the sum of all elements and keep it in variable sum. We will get the missing number by s-sum (As sum doesn't includes the missing number).
To find the common difference(diff) in a nearly complete arithmetic progression. We first checks if the difference between the first two elements matches the last two elements, if so, it uses that. If not, it checks whether the first difference equals the expected average step. If both fail, it falls back to the last difference
C++ // C++ program to find the missing number // in a given arithmetic progression #include <iostream> #include <vector> using namespace std; int findMissing(vector<int> &arr) { int n = arr.size(); int diff = (arr[1] - arr[0] == arr[n-1] - arr[n-2]) ? arr[1] - arr[0] : ((arr[1] - arr[0] == (arr[n-1] - arr[0])/n) ? arr[1] - arr[0] : arr[n-1] - arr[n-2]); if (diff == 0) return arr[0]; // Calculate the expected sum of the progression long long s = (2LL * arr[0] + n * diff) * (n + 1) / 2; // Calculate the sum of all elements in the array int sum = 0; for (int i = 0; i <= n - 1; i++) { sum = sum + arr[i]; } return s - sum; } int main() { vector<int> arr = {2, 4, 8, 10, 12, 14}; cout << findMissing(arr); return 0; } // Java program to find the missing number // in a given arithmetic progression class GfG { static int findMissing(int[] arr) { int n = arr.length; int diff = (arr[1] - arr[0] == arr[n-1] - arr[n-2]) ? arr[1] - arr[0] : ((arr[1] - arr[0] == (arr[n-1] - arr[0]) / n) ? arr[1] - arr[0] : arr[n-1] - arr[n-2]); if (diff == 0) return arr[0]; // Calculate the expected sum of the progression int s = (int) (((2L * arr[0] + (long) n * diff) * (n + 1)) / 2); int sum = 0; // Calculate the sum of all elements in the array for (int num : arr) { sum += num; } // The missing number is the difference between the two sums return s - sum; } public static void main(String[] args) { int[] arr = {2, 4, 8, 10, 12, 14}; System.out.println(findMissing(arr)); } } # Python program to find the missing number # in a given arithmetic progression def findMissing(arr): n = len(arr) diff1 = arr[1] - arr[0] diff2 = arr[-1] - arr[-2] diff3 = (arr[-1] - arr[0]) // n if diff1 == diff2: diff = diff1 elif diff1 == diff3: diff = diff1 else: diff = diff2 if diff == 0: return arr[0] s = ((2 * arr[0] + (len(arr)) * diff) * (len(arr)+1)) // 2 # The missing number is the difference between # the expected sum and the actual sum missing = s - sum(arr) return int(missing) if __name__ == "__main__": arr = [2, 4, 8, 10, 12, 14] missing = findMissing(arr) print(missing)
// C# program to find the missing number // in a given arithmetic progression using System; class GfG { static int findMissing(int[] arr) { int n = arr.Length; int diff = (arr[1] - arr[0] == arr[n-1] - arr[n-2]) ? arr[1] - arr[0] : ((arr[1] - arr[0] == (arr[n-1] - arr[0]) / n) ? arr[1] - arr[0] : arr[n-1] - arr[n-2]); if (diff == 0) return arr[0]; // Calculate the expected sum of the progression int s = (int)(((2L * arr[0] + (long) n * diff) * (n + 1)) / 2); // Calculate the actual sum of the array int sum = 0; foreach(int num in arr) { sum += num; } // The missing number is the difference return s - sum; } static void Main(string[] args) { int[] arr = { 2, 4, 8, 10, 12, 14 }; Console.WriteLine(findMissing(arr)); } } // JavaScript program to find the missing number // in a given arithmetic progression function findMissing(arr) { let n = arr.length; let diff = (arr[1] - arr[0] == arr[n-1] - arr[n-2]) ? arr[1] - arr[0] : ((arr[1] - arr[0] == (arr[n-1] - arr[0])/n) ? arr[1] - arr[0] : arr[n-1] - arr[n-2]); if (diff === 0) return arr[0]; const totalSum = ((2 * arr[0] + (arr.length) * diff) * (arr.length +1))/ 2; let sum = 0; // Calculate the actual sum of the array for (let i = 0; i < n; i++) { sum += arr[i]; } // The missing number is the difference return totalSum - sum; } let arr = [ 2, 4, 8, 10, 12, 14 ]; console.log(findMissing(arr)); [Expected Approach] Using Binary Search (Recursive) – O(log n) Time and O(1) Space
The idea is to go to the middle element. Check if the difference between middle and next to middle is equal to diff or not, if not then the missing element lies between mid and mid+1. If the middle element is equal to (n/2)th term in Arithmetic Series, then missing element lies in right half. Else element lies in left half.
C++ // C++ program to find the missing number // in a given arithmetic progression #include <iostream> #include <vector> #include <climits> using namespace std; // A binary search based recursive function that returns // the missing element in arithmetic progression int findMissingUtil(vector<int> &arr, int low, int high, int diff) { if (high <= low) return INT_MAX; // Find index of middle element int mid = low + (high - low) / 2; // The element just after the middle element is missing. // The arr[mid+1] must exist, because we return when // (low == high) and take floor of (high-low)/2 if (arr[mid + 1] - arr[mid] != diff) return (arr[mid] + diff); // The element just before mid is missing if (mid > 0 && arr[mid] - arr[mid - 1] != diff) return (arr[mid - 1] + diff); // If the elements till mid follow AP, then recur // for right half if (arr[mid] == arr[0] + mid * diff) return findMissingUtil(arr, mid + 1, high, diff); // Else recur for left half return findMissingUtil(arr, low, mid - 1, diff); } int findMissing(vector<int> &arr) { int n = arr.size(); int diff = (arr[1] - arr[0] == arr[n-1] - arr[n-2]) ? arr[1] - arr[0] : ((arr[1] - arr[0] == (arr[n-1] - arr[0])/n) ? arr[1] - arr[0] : arr[n-1] - arr[n-2]); if (diff == 0) return arr[0]; // Calculate the common difference using the first // and last elements int res = findMissingUtil(arr, 0, n - 1, diff); return (res == INT_MAX)?(arr[0] + (n)*diff):res; } int main() { vector<int> arr = {2, 4, 8, 10, 12, 14}; cout << findMissing(arr); return 0; } // A Java program to find the missing number in // a given arithmetic progression class GfG { // A binary search based recursive function that returns // the missing element in arithmetic progression static int findMissingUtil(int[] arr, int low, int high, int diff) { // There must be at least two elements to find the // missing element if (high <= low) return Integer.MAX_VALUE; // Find index of the middle element int mid = low + (high - low) / 2; // If the element just after the middle element is // missing if (arr[mid + 1] - arr[mid] != diff) return (arr[mid] + diff); // If the element just before mid is missing if (mid > 0 && arr[mid] - arr[mid - 1] != diff) return (arr[mid - 1] + diff); // If the elements till mid follow the arithmetic // progression, recur for the right half if (arr[mid] == arr[0] + mid * diff) return findMissingUtil(arr, mid + 1, high, diff); // Else recur for the left half return findMissingUtil(arr, low, mid - 1, diff); } // Function to find the missing element in the // arithmetic progression static int findMissing(int[] arr) { int n = arr.length; int diff = (arr[1] - arr[0] == arr[n-1] - arr[n-2]) ? arr[1] - arr[0] : ((arr[1] - arr[0] == (arr[n-1] - arr[0])/n) ? arr[1] - arr[0] : arr[n-1] - arr[n-2]); if (diff == 0) return arr[0]; // Calculate the common difference using the first // and last elements int res = findMissingUtil(arr, 0, n - 1, diff); return (res == Integer.MAX_VALUE)?(arr[0] + (n)*diff):res; } public static void main(String[] args) { int[] arr = { 2, 4, 8, 10, 12, 14 }; System.out.println(findMissing(arr)); } } # A Python3 program to find the missing # number in a given arithmetic progression import sys # A binary search based recursive function that returns # the missing element in arithmetic progression def findMissingUtil(arr, low, high, diff): if high <= low: return sys.maxsize # Find index of middle element mid = (low + high) // 2 # The element just after the middle element is missing if arr[mid + 1] - arr[mid] != diff: return arr[mid] + diff # The element just before mid is missing if mid > 0 and arr[mid] - arr[mid - 1] != diff: return arr[mid - 1] + diff # If the elements till mid follow AP, then recur for right half if arr[mid] == arr[0] + mid * diff: return findMissingUtil(arr, mid + 1, high, diff) # Else recur for left half return findMissingUtil(arr, low, mid - 1, diff) # Function to find the missing element in AP def findMissing(arr): n = len(arr) # Calculate the common difference diff1 = arr[1] - arr[0] diff2 = arr[-1] - arr[-2] diff3 = (arr[-1] - arr[0]) // n if diff1 == diff2: diff = diff1 elif diff1 == diff3: diff = diff1 else: diff = diff2 if diff == 0: return arr[0] # Calculate the common difference using the first # and last elements res = findMissingUtil(arr, 0, n - 1, diff); if res == sys.maxsize: return arr[0] + n * diff else: return res if __name__ == "__main__": arr = [2, 4, 8, 10, 12, 14] print(findMissing(arr))
// A C# program to find the missing // number in a given arithmetic progression using System; class GfG { // A binary search based recursive function that returns // the missing element in arithmetic progression static int findMissingUtil(int[] arr, int low, int high, int diff) { // There must be two elements to find the missing if (high <= low) return int.MaxValue; // Find index of middle element int mid = low + (high - low) / 2; // The element just after the middle element is // missing if (arr[mid + 1] - arr[mid] != diff) return arr[mid] + diff; // The element just before mid is missing if (mid > 0 && arr[mid] - arr[mid - 1] != diff) return arr[mid - 1] + diff; // If the elements till mid follow AP, then recur // for right half if (arr[mid] == arr[0] + mid * diff) return findMissingUtil(arr, mid + 1, high, diff); // Else recur for left half return findMissingUtil(arr, low, mid - 1, diff); } static int findMissing(int[] arr) { int n = arr.Length; int diff = (arr[1] - arr[0] == arr[n-1] - arr[n-2]) ? arr[1] - arr[0] : ((arr[1] - arr[0] == (arr[n-1] - arr[0]) / n) ? arr[1] - arr[0] : arr[n-1] - arr[n-2]); if (diff == 0) return arr[0]; // Calculate the common difference using the first // and last elements int res = findMissingUtil(arr, 0, n - 1, diff); return (res == int.MaxValue)?(arr[0] + (n)*diff):res; } static void Main() { int[] arr = { 2, 4, 8, 10, 12, 14 }; Console.WriteLine(findMissing(arr)); } }; // A Javascript program to find the missing number in a // given arithmetic progression // A binary search based recursive function that returns // the missing element in arithmetic progression function findMissingUtil(arr, low, high, diff) { // There must be two elements to find the missing if (high <= low) return Number.MAX_VALUE; // Find index of middle element let mid = low + Math.floor((high - low) / 2); // The element just after the middle element is missing if (arr[mid + 1] - arr[mid] !== diff) return arr[mid] + diff; // The element just before mid is missing if (mid > 0 && arr[mid] - arr[mid - 1] !== diff) return arr[mid - 1] + diff; // If the elements till mid follow AP, then recur for // right half if (arr[mid] === arr[0] + mid * diff) return findMissingUtil(arr, mid + 1, high, diff); // Else recur for left half return findMissingUtil(arr, low, mid - 1, diff); } function findMissing(arr) { let n = arr.length; let diff = (arr[1] - arr[0] == arr[n-1] - arr[n-2]) ? arr[1] - arr[0] : ((arr[1] - arr[0] == (arr[n-1] - arr[0])/n) ? arr[1] - arr[0] : arr[n-1] - arr[n-2]); if (diff == 0) return arr[0]; // Calculate the common difference using the first // and last elements let res = findMissingUtil(arr, 0, n - 1, diff); return (res == Number.MAX_VALUE)?(arr[0] + (n)*diff):res; } let arr = [ 2, 4, 8, 10, 12, 14 ]; console.log(findMissing(arr)); [Alternate Approach] Using Binary Search (Iterative) – O(log n) Time and O(1) Space
The idea is to go to the middle element and check whether the index of middle element is equal to (nth position of middle element in AP) minus 1. If so then the missing element lies at right half and if not then the missing element lies at left half (this idea is similar to Find the only repeating element in a sorted array of size n).
After breaking out of binary search loop the missing element will lie between indices high and low. We can find the missing element by adding the common difference with element at index high or by subtracting the common difference with element at index low.
C++ // C++ program to find the missing number // in a given arithmetic progression #include<iostream> #include<vector> #include <climits> using namespace std; int findMissing(vector<int> &arr) { int n = arr.size(); // If exactly one element is missing, then we can find // difference of arithmetic progression using following // formula. int diff = (arr[1] - arr[0] == arr[n-1] - arr[n-2]) ? arr[1] - arr[0] : ((arr[1] - arr[0] == (arr[n-1] - arr[0])/n) ? arr[1] - arr[0] : arr[n-1] - arr[n-2]); if(diff == 0) return arr[0]; int lo = 0, hi = n - 1; while (lo <= hi) { int mid = (lo + hi) / 2; // if mid == (nth position of element in AP)-1 // the missing element will exist in right half if ((arr[mid] - arr[0]) / diff == mid) lo = mid + 1; // the missing element will exist in left half else hi = mid - 1; } // after breaking out of binary search loop the missing element // will exist between high and low return arr[hi] + diff; } int main() { vector<int> arr = {2, 4, 8, 10, 12, 14}; cout << findMissing(arr); return 0; } // Java program to find the missing number // in a given arithmetic progression import java.util.*; class GfG { static int findMissing(int[] arr) { int n = arr.length; // If exactly one element is missing, then we can find // difference of arithmetic progression using following // formula. int diff = (arr[1] - arr[0] == arr[n-1] - arr[n-2]) ? arr[1] - arr[0] : ((arr[1] - arr[0] == (arr[n-1] - arr[0])/n) ? arr[1] - arr[0] : arr[n-1] - arr[n-2]); if (diff == 0) return arr[0]; int lo = 0, hi = n - 1; while (lo <= hi) { int mid = (lo + hi) / 2; // if mid == (nth position of element in AP)-1 // the missing element will exist in right half if ((arr[mid] - arr[0]) / diff == mid) lo = mid + 1; // the missing element will exist in left half else hi = mid - 1; } // after breaking out of binary search loop the missing element // will exist between high and low return arr[hi] + diff; } public static void main(String[] args) { int[] arr = {2, 4, 8, 10, 12, 14}; System.out.println(findMissing(arr)); } } # Python program to find the missing number # in a given arithmetic progression def findMissing(arr): n = len(arr) # If exactly one element is missing, then we can find # difference of arithmetic progression using following # formula. diff1 = arr[1] - arr[0] diff2 = arr[-1] - arr[-2] diff3 = (arr[-1] - arr[0]) // n if diff1 == diff2: diff = diff1 elif diff1 == diff3: diff = diff1 else: diff = diff2 if diff == 0: return arr[0] lo, hi = 0, n - 1 while lo <= hi: mid = (lo + hi) // 2 # if mid == (nth position of element in AP)-1 # the missing element will exist in right half if (arr[mid] - arr[0]) // diff == mid: lo = mid + 1 # the missing element will exist in left half else: hi = mid - 1 # after breaking out of binary search loop the missing element # will exist between high and low return arr[hi] + diff if __name__ == "__main__": arr = [2, 4, 8, 10, 12, 14] print(findMissing(arr))
// C# program to find the missing number // in a given arithmetic progression using System; class GfG { static int findMissing(int[] arr) { int n = arr.Length; // If exactly one element is missing, then we can find // difference of arithmetic progression using following // formula. int diff = (arr[1] - arr[0] == arr[n-1] - arr[n-2]) ? arr[1] - arr[0] : ((arr[1] - arr[0] == (arr[n-1] - arr[0]) / n) ? arr[1] - arr[0] : arr[n-1] - arr[n-2]); if (diff == 0) return arr[0]; int lo = 0, hi = n - 1; while (lo <= hi) { int mid = (lo + hi) / 2; // if mid == (nth position of element in AP)-1 // the missing element will exist in right half if ((arr[mid] - arr[0]) / diff == mid) lo = mid + 1; // the missing element will exist in left half else hi = mid - 1; } // after breaking out of binary search loop the missing element // will exist between high and low return arr[hi] + diff; } static void Main() { int[] arr = {2, 4, 8, 10, 12, 14}; Console.WriteLine(findMissing(arr)); } } // JavaScript program to find the missing number // in a given arithmetic progression function findMissing(arr) { let n = arr.length; // If exactly one element is missing, then we can find // difference of arithmetic progression using following // formula. let diff = (arr[1] - arr[0] == arr[n-1] - arr[n-2]) ? arr[1] - arr[0] : ((arr[1] - arr[0] == (arr[n-1] - arr[0])/n) ? arr[1] - arr[0] : arr[n-1] - arr[n-2]); if (diff == 0) return arr[0]; let lo = 0, hi = n - 1; while (lo <= hi) { let mid = Math.floor((lo + hi) / 2); // if mid == (nth position of element in AP)-1 // the missing element will exist in right half if (Math.floor((arr[mid] - arr[0]) / diff) === mid) lo = mid + 1; // the missing element will exist in left half else hi = mid - 1; } // after breaking out of binary search loop the missing element // will exist between high and low return arr[hi] + diff; } let arr = [2, 4, 8, 10, 12, 14]; console.log(findMissing(arr));
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem
My Profile