Find the missing number in arithmetic progression
An arithmetic progression is a sequence of numbers in which each term is obtained by adding a fixed number (called the common difference) to the preceding term. For example, 2, 4, 6, 8, 10 is an arithmetic progression with a common difference of 2.
The missing number in an arithmetic progression can be found using the divide and conquer approach. Here's how:
Calculate the middle term of the sequence using the formula: middle term = (first term + last term) / 2 where the first term is the first number in the sequence, the last term is the last number in the sequence, and the middle term is the number in the middle of the sequence.
Calculate the difference between the middle term and the first term of the sequence. This gives us the expected common difference between consecutive terms in the sequence.
Check if the middle term is the missing number in the sequence. If it is, then we have found the missing number.
If the middle term is not the missing number, then we need to check which half of the sequence the missing number is in. If the difference between the middle term and the first term is equal to the expected common difference, then the missing number is in the second half of the sequence. Otherwise, the missing number is in the first half of the sequence.
Repeat steps 1-4 for the half of the sequence that the missing number is in.
Continue the process until the missing number is found.
This approach is efficient because it reduces the search space by half with each iteration, leading to a logarithmic time complexity of O(log n), where n is the length of the sequence.
Here given code implementation process.
// C program for
// Find the missing number in arithmetic progression
#include <stdio.h>
int missingNo(int series[], int low, int high, int interval)
{
if (low >= high)
{
// When no result
return -1;
}
// Find middle element
int mid = low + (high - low) / 2;
if (mid + 1 <= high && (series[mid + 1] - series[mid]) != interval)
{
return series[mid] + interval;
}
if (mid > 0 && (series[mid] - series[mid - 1]) != interval)
{
return series[mid - 1] + interval;
}
if ((mid *interval) + series[0] == series[mid])
{
// When the middle position element is a valid element
// of the given arithmetic progression.
// Check sequence of right-sided elements from middle.
return missingNo(series, mid + 1, high, interval);
}
// Check sequence of left-sided elements from middle.
return missingNo(series, low, mid - 1, interval);
}
void missingArithmeticPro(int series[], int n)
{
if (n > 1)
{
// When n is more than 1
// Find interval between sequence
int interval = (series[n - 1] - series[0]) / n;
// Find missing element
int value = missingNo(series, 0, n - 1, interval);
// Display missing element
printf("\n %d", value);
}
}
int main(int argc, char
const *argv[])
{
// Arithmetic progression series with one missing element
int a[] = {
1 , 4 , 7 , 13 , 16 , 19
};
int b[] = {
6 , 12 , 18 , 30 , 36 , 42 , 48 , 54 , 60 , 66
};
int c[] = {
2 , 5 , 11 , 14
};
// Note : Here first and last elements
// are not considered as missing.
// Test A
int n = sizeof(a) / sizeof(a[0]);
missingArithmeticPro(a, n);
// Test B
n = sizeof(b) / sizeof(b[0]);
missingArithmeticPro(b, n);
// Test C
n = sizeof(c) / sizeof(c[0]);
missingArithmeticPro(c, n);
return 0;
}
Output
10
24
8
/*
Java program
Find the missing number in arithmetic progression
*/
public class ArithmeticProgression
{
public int missingNo(int[] series, int low, int high, int interval)
{
if (low >= high)
{
// When no result
return -1;
}
// Find middle element
int mid = low + (high - low) / 2;
if (mid + 1 <= high && (series[mid + 1] - series[mid]) != interval)
{
return series[mid] + interval;
}
if (mid > 0 && (series[mid] - series[mid - 1]) != interval)
{
return series[mid - 1] + interval;
}
if ((mid * interval) + series[0] == series[mid])
{
// When the middle position element is a valid element
// of the given arithmetic progression.
// Check sequence of right-sided elements from middle.
return missingNo(series, mid + 1, high, interval);
}
// Check sequence of left-sided elements from middle.
return missingNo(series, low, mid - 1, interval);
}
public void missingArithmeticPro(int[] series, int n)
{
if (n > 1)
{
// When n is more than 1
// Find interval between sequence
int interval = (series[n - 1] - series[0]) / n;
// Find missing element
int value = missingNo(series, 0, n - 1, interval);
// Display missing element
System.out.print("\n " + value);
}
}
public static void main(String[] args)
{
ArithmeticProgression task = new ArithmeticProgression();
// Arithmetic progression series with one missing element
int[] a = {
1 , 4 , 7 , 13 , 16 , 19
};
int[] b = {
6 , 12 , 18 , 30 , 36 , 42 , 48 , 54 , 60 , 66
};
int[] c = {
2 , 5 , 11 , 14
};
// Note : Here first and last elements
// are not considered as missing.
// Test A
int n = a.length;
task.missingArithmeticPro(a, n);
// Test B
n = b.length;
task.missingArithmeticPro(b, n);
// Test C
n = c.length;
task.missingArithmeticPro(c, n);
}
}
Output
10
24
8
// Include header file
#include <iostream>
using namespace std;
/*
C++ program
Find the missing number in arithmetic progression
*/
class ArithmeticProgression
{
public: int missingNo(int series[],
int low,
int high,
int interval)
{
if (low >= high)
{
// When no result
return -1;
}
// Find middle element
int mid = low + (high - low) / 2;
if (mid + 1 <= high && (series[mid + 1] - series[mid]) != interval)
{
return series[mid] + interval;
}
if (mid > 0 && (series[mid] - series[mid - 1]) != interval)
{
return series[mid - 1] + interval;
}
if ((mid *interval) + series[0] == series[mid])
{
// When the middle position element is a valid element
// of the given arithmetic progression.
// Check sequence of right-sided elements from middle.
return this->missingNo(series, mid + 1, high, interval);
}
// Check sequence of left-sided elements from middle.
return this->missingNo(series, low, mid - 1, interval);
}
void missingArithmeticPro(int series[], int n)
{
if (n > 1)
{
// When n is more than 1
// Find interval between sequence
int interval = (series[n - 1] - series[0]) / n;
// Find missing element
int value = this->missingNo(series, 0, n - 1, interval);
// Display missing element
cout << "\n " << value;
}
}
};
int main()
{
ArithmeticProgression *task = new ArithmeticProgression();
// Arithmetic progression series with one missing element
int a[] = {
1 , 4 , 7 , 13 , 16 , 19
};
int b[] = {
6 , 12 , 18 , 30 , 36 , 42 , 48 , 54 , 60 , 66
};
int c[] = {
2 , 5 , 11 , 14
};
// Note : Here first and last elements
// are not considered as missing.
// Test A
int n = sizeof(a) / sizeof(a[0]);
task->missingArithmeticPro(a, n);
// Test B
n = sizeof(b) / sizeof(b[0]);
task->missingArithmeticPro(b, n);
// Test C
n = sizeof(c) / sizeof(c[0]);
task->missingArithmeticPro(c, n);
return 0;
}
Output
10
24
8
// Include namespace system
using System;
/*
Csharp program
Find the missing number in arithmetic progression
*/
public class ArithmeticProgression
{
public int missingNo(int[] series,
int low,
int high,
int interval)
{
if (low >= high)
{
// When no result
return -1;
}
// Find middle element
int mid = low + (high - low) / 2;
if (mid + 1 <= high && (series[mid + 1] - series[mid]) != interval)
{
return series[mid] + interval;
}
if (mid > 0 && (series[mid] - series[mid - 1]) != interval)
{
return series[mid - 1] + interval;
}
if ((mid * interval) + series[0] == series[mid])
{
// When the middle position element is a valid element
// of the given arithmetic progression.
// Check sequence of right-sided elements from middle.
return this.missingNo(series, mid + 1, high, interval);
}
// Check sequence of left-sided elements from middle.
return this.missingNo(series, low, mid - 1, interval);
}
public void missingArithmeticPro(int[] series, int n)
{
if (n > 1)
{
// When n is more than 1
// Find interval between sequence
int interval = (series[n - 1] - series[0]) / n;
// Find missing element
int value = this.missingNo(series, 0, n - 1, interval);
// Display missing element
Console.Write("\n " + value);
}
}
public static void Main(String[] args)
{
ArithmeticProgression task = new ArithmeticProgression();
// Arithmetic progression series with one missing element
int[] a = {
1 , 4 , 7 , 13 , 16 , 19
};
int[] b = {
6 , 12 , 18 , 30 , 36 , 42 , 48 , 54 , 60 , 66
};
int[] c = {
2 , 5 , 11 , 14
};
// Note : Here first and last elements
// are not considered as missing.
// Test A
int n = a.Length;
task.missingArithmeticPro(a, n);
// Test B
n = b.Length;
task.missingArithmeticPro(b, n);
// Test C
n = c.Length;
task.missingArithmeticPro(c, n);
}
}
Output
10
24
8
package main
import "fmt"
/*
Go program
Find the missing number in arithmetic progression
*/
type ArithmeticProgression struct {}
func getArithmeticProgression() * ArithmeticProgression {
var me *ArithmeticProgression = &ArithmeticProgression {}
return me
}
func(this ArithmeticProgression) missingNo(series[] int,
low int, high int, interval int) int {
if low >= high {
// When no result
return -1
}
// Find middle element
var mid int = low + (high - low) / 2
if mid + 1 <= high && (series[mid + 1] - series[mid]) != interval {
return series[mid] + interval
}
if mid > 0 && (series[mid] - series[mid - 1]) != interval {
return series[mid - 1] + interval
}
if (mid * interval) + series[0] == series[mid] {
// When the middle position element is a valid element
// of the given arithmetic progression.
// Check sequence of right-sided elements from middle.
return this.missingNo(series, mid + 1, high, interval)
}
// Check sequence of left-sided elements from middle.
return this.missingNo(series, low, mid - 1, interval)
}
func(this ArithmeticProgression) missingArithmeticPro(series[] int, n int) {
if n > 1 {
// When n is more than 1
// Find interval between sequence
var interval int = (series[n - 1] - series[0]) / n
// Find missing element
var value int = this.missingNo(series, 0, n - 1, interval)
// Display missing element
fmt.Print("\n ", value)
}
}
func main() {
var task * ArithmeticProgression = getArithmeticProgression()
// Arithmetic progression series with one missing element
var a = [] int {
1,
4,
7,
13,
16,
19,
}
var b = [] int {
6,
12,
18,
30,
36,
42,
48,
54,
60,
66,
}
var c = [] int {
2,
5,
11,
14,
}
// Note : Here first and last elements
// are not considered as missing.
// Test A
var n int = len(a)
task.missingArithmeticPro(a, n)
// Test B
n = len(b)
task.missingArithmeticPro(b, n)
// Test C
n = len(c)
task.missingArithmeticPro(c, n)
}
Output
10
24
8
<?php
/*
Php program
Find the missing number in arithmetic progression
*/
class ArithmeticProgression
{
public function missingNo($series, $low, $high, $interval)
{
if ($low >= $high)
{
// When no result
return -1;
}
// Find middle element
$mid = $low + (int)(($high - $low) / 2);
if ($mid + 1 <= $high &&
($series[$mid + 1] - $series[$mid]) != $interval)
{
return $series[$mid] + $interval;
}
if ($mid > 0 &&
($series[$mid] - $series[$mid - 1]) != $interval)
{
return $series[$mid - 1] + $interval;
}
if (($mid * $interval) + $series[0] == $series[$mid])
{
// When the middle position element is a valid element
// of the given arithmetic progression.
// Check sequence of right-sided elements from middle.
return $this->missingNo($series, $mid + 1, $high, $interval);
}
// Check sequence of left-sided elements from middle.
return $this->missingNo($series, $low, $mid - 1, $interval);
}
public function missingArithmeticPro($series, $n)
{
if ($n > 1)
{
// When n is more than 1
// Find interval between sequence
$interval = (int)(($series[$n - 1] - $series[0]) / $n);
// Find missing element
$value = $this->missingNo($series, 0, $n - 1, $interval);
// Display missing element
echo("\n ".$value);
}
}
}
function main()
{
$task = new ArithmeticProgression();
// Arithmetic progression series with one missing element
$a = array(1, 4, 7, 13, 16, 19);
$b = array(6, 12, 18, 30, 36, 42, 48, 54, 60, 66);
$c = array(2, 5, 11, 14);
// Note : Here first and last elements
// are not considered as missing.
// Test A
$n = count($a);
$task->missingArithmeticPro($a, $n);
// Test B
$n = count($b);
$task->missingArithmeticPro($b, $n);
// Test C
$n = count($c);
$task->missingArithmeticPro($c, $n);
}
main();
Output
10
24
8
/*
Node JS program
Find the missing number in arithmetic progression
*/
class ArithmeticProgression
{
missingNo(series, low, high, interval)
{
if (low >= high)
{
// When no result
return -1;
}
// Find middle element
var mid = low + parseInt((high - low) / 2);
if (mid + 1 <= high && (series[mid + 1] - series[mid]) != interval)
{
return series[mid] + interval;
}
if (mid > 0 && (series[mid] - series[mid - 1]) != interval)
{
return series[mid - 1] + interval;
}
if ((mid * interval) + series[0] == series[mid])
{
// When the middle position element is a valid element
// of the given arithmetic progression.
// Check sequence of right-sided elements from middle.
return this.missingNo(series, mid + 1, high, interval);
}
// Check sequence of left-sided elements from middle.
return this.missingNo(series, low, mid - 1, interval);
}
missingArithmeticPro(series, n)
{
if (n > 1)
{
// When n is more than 1
// Find interval between sequence
var interval = parseInt((series[n - 1] - series[0]) / n);
// Find missing element
var value = this.missingNo(series, 0, n - 1, interval);
// Display missing element
process.stdout.write("\n " + value);
}
}
}
function main()
{
var task = new ArithmeticProgression();
// Arithmetic progression series with one missing element
var a = [1, 4, 7, 13, 16, 19];
var b = [6, 12, 18, 30, 36, 42, 48, 54, 60, 66];
var c = [2, 5, 11, 14];
// Note : Here first and last elements
// are not considered as missing.
// Test A
var n = a.length;
task.missingArithmeticPro(a, n);
// Test B
n = b.length;
task.missingArithmeticPro(b, n);
// Test C
n = c.length;
task.missingArithmeticPro(c, n);
}
main();
Output
10
24
8
# Python 3 program
# Find the missing number in arithmetic progression
class ArithmeticProgression :
def missingNo(self, series, low, high, interval) :
if (low >= high) :
# When no result
return -1
# Find middle element
mid = low + int((high - low) / 2)
if (mid + 1 <= high and(series[mid + 1] - series[mid]) != interval) :
return series[mid] + interval
if (mid > 0 and(series[mid] - series[mid - 1]) != interval) :
return series[mid - 1] + interval
if ((mid * interval) + series[0] == series[mid]) :
# When the middle position element is a valid element
# of the given arithmetic progression.
# Check sequence of right-sided elements from middle.
return self.missingNo(series, mid + 1, high, interval)
# Check sequence of left-sided elements from middle.
return self.missingNo(series, low, mid - 1, interval)
def missingArithmeticPro(self, series, n) :
if (n > 1) :
# When n is more than 1
# Find interval between sequence
interval = int((series[n - 1] - series[0]) / n)
# Find missing element
value = self.missingNo(series, 0, n - 1, interval)
# Display missing element
print("\n ", value, end = "")
def main() :
task = ArithmeticProgression()
# Arithmetic progression series with one missing element
a = [1, 4, 7, 13, 16, 19]
b = [6, 12, 18, 30, 36, 42, 48, 54, 60, 66]
c = [2, 5, 11, 14]
# Note : Here first and last elements
# are not considered as missing.
# Test A
n = len(a)
task.missingArithmeticPro(a, n)
# Test B
n = len(b)
task.missingArithmeticPro(b, n)
# Test C
n = len(c)
task.missingArithmeticPro(c, n)
if __name__ == "__main__": main()
Output
10
24
8
# Ruby program
# Find the missing number in arithmetic progression
class ArithmeticProgression
def missingNo(series, low, high, interval)
if (low >= high)
# When no result
return -1
end
# Find middle element
mid = low + (high - low) / 2
if (mid + 1 <= high && (series[mid + 1] - series[mid]) != interval)
return series[mid] + interval
end
if (mid > 0 && (series[mid] - series[mid - 1]) != interval)
return series[mid - 1] + interval
end
if ((mid * interval) + series[0] == series[mid])
# When the middle position element is a valid element
# of the given arithmetic progression.
# Check sequence of right-sided elements from middle.
return self.missingNo(series, mid + 1, high, interval)
end
# Check sequence of left-sided elements from middle.
return self.missingNo(series, low, mid - 1, interval)
end
def missingArithmeticPro(series, n)
if (n > 1)
# When n is more than 1
# Find interval between sequence
interval = (series[n - 1] - series[0]) / n
# Find missing element
value = self.missingNo(series, 0, n - 1, interval)
# Display missing element
print("\n ", value)
end
end
end
def main()
task = ArithmeticProgression.new()
# Arithmetic progression series with one missing element
a = [1, 4, 7, 13, 16, 19]
b = [6, 12, 18, 30, 36, 42, 48, 54, 60, 66]
c = [2, 5, 11, 14]
# Note : Here first and last elements
# are not considered as missing.
# Test A
n = a.length
task.missingArithmeticPro(a, n)
# Test B
n = b.length
task.missingArithmeticPro(b, n)
# Test C
n = c.length
task.missingArithmeticPro(c, n)
end
main()
Output
10
24
8
/*
Scala program
Find the missing number in arithmetic progression
*/
class ArithmeticProgression()
{
def missingNo(series: Array[Int], low: Int,
high: Int, interval: Int): Int = {
if (low >= high)
{
// When no result
return -1;
}
// Find middle element
var mid: Int = low + (high - low) / 2;
if (mid + 1 <= high && (series(mid + 1) - series(mid)) != interval)
{
return series(mid) + interval;
}
if (mid > 0 && (series(mid) - series(mid - 1)) != interval)
{
return series(mid - 1) + interval;
}
if ((mid * interval) + series(0) == series(mid))
{
// When the middle position element is a valid element
// of the given arithmetic progression.
// Check sequence of right-sided elements from middle.
return missingNo(series, mid + 1, high, interval);
}
// Check sequence of left-sided elements from middle.
return missingNo(series, low, mid - 1, interval);
}
def missingArithmeticPro(series: Array[Int], n: Int): Unit = {
if (n > 1)
{
// When n is more than 1
// Find interval between sequence
var interval: Int = (series(n - 1) - series(0)) / n;
// Find missing element
var value: Int = missingNo(series, 0, n - 1, interval);
// Display missing element
print("\n " + value);
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: ArithmeticProgression = new ArithmeticProgression();
// Arithmetic progression series with one missing element
var a: Array[Int] = Array(1, 4, 7, 13, 16, 19);
var b: Array[Int] = Array(6, 12, 18, 30, 36, 42, 48, 54, 60, 66);
var c: Array[Int] = Array(2, 5, 11, 14);
// Note : Here first and last elements
// are not considered as missing.
// Test A
var n: Int = a.length;
task.missingArithmeticPro(a, n);
// Test B
n = b.length;
task.missingArithmeticPro(b, n);
// Test C
n = c.length;
task.missingArithmeticPro(c, n);
}
}
Output
10
24
8
import Foundation;
/*
Swift 4 program
Find the missing number in arithmetic progression
*/
class ArithmeticProgression
{
func missingNo(_ series: [Int],
_ low: Int, _ high: Int, _ interval: Int) -> Int
{
if (low >= high)
{
// When no result
return -1;
}
// Find middle element
let mid: Int = low + (high - low) / 2;
if (mid + 1 <= high && (series[mid + 1] - series[mid]) != interval)
{
return series[mid] + interval;
}
if (mid > 0 && (series[mid] - series[mid - 1]) != interval)
{
return series[mid - 1] + interval;
}
if ((mid * interval) + series[0] == series[mid])
{
// When the middle position element is a valid element
// of the given arithmetic progression.
// Check sequence of right-sided elements from middle.
return self.missingNo(series, mid + 1, high, interval);
}
// Check sequence of left-sided elements from middle.
return self.missingNo(series, low, mid - 1, interval);
}
func missingArithmeticPro(_ series: [Int], _ n: Int)
{
if (n > 1)
{
// When n is more than 1
// Find interval between sequence
let interval: Int = (series[n - 1] - series[0]) / n;
// Find missing element
let value: Int = self.missingNo(series, 0, n - 1, interval);
// Display missing element
print("\n ", value, terminator: "");
}
}
}
func main()
{
let task: ArithmeticProgression = ArithmeticProgression();
// Arithmetic progression series with one missing element
let a: [Int] = [1, 4, 7, 13, 16, 19];
let b: [Int] = [6, 12, 18, 30, 36, 42, 48, 54, 60, 66];
let c: [Int] = [2, 5, 11, 14];
// Note : Here first and last elements
// are not considered as missing.
// Test A
var n: Int = a.count;
task.missingArithmeticPro(a, n);
// Test B
n = b.count;
task.missingArithmeticPro(b, n);
// Test C
n = c.count;
task.missingArithmeticPro(c, n);
}
main();
Output
10
24
8
/*
Kotlin program
Find the missing number in arithmetic progression
*/
class ArithmeticProgression
{
fun missingNo(series: Array < Int > ,
low: Int, high: Int, interval: Int): Int
{
if (low >= high)
{
// When no result
return -1;
}
// Find middle element
val mid: Int = low + (high - low) / 2;
if (mid + 1 <= high && (series[mid + 1] - series[mid]) != interval)
{
return series[mid] + interval;
}
if (mid > 0 && (series[mid] - series[mid - 1]) != interval)
{
return series[mid - 1] + interval;
}
if ((mid * interval) + series[0] == series[mid])
{
// When the middle position element is a valid element
// of the given arithmetic progression.
// Check sequence of right-sided elements from middle.
return this.missingNo(series, mid + 1, high, interval);
}
// Check sequence of left-sided elements from middle.
return this.missingNo(series, low, mid - 1, interval);
}
fun missingArithmeticPro(series: Array < Int > , n: Int): Unit
{
if (n > 1)
{
// When n is more than 1
// Find interval between sequence
val interval: Int = (series[n - 1] - series[0]) / n;
// Find missing element
val value: Int = this.missingNo(series, 0, n - 1, interval);
// Display missing element
print("\n " + value);
}
}
}
fun main(args: Array < String > ): Unit
{
val task: ArithmeticProgression = ArithmeticProgression();
// Arithmetic progression series with one missing element
val a: Array < Int > = arrayOf(1, 4, 7, 13, 16, 19);
val b: Array < Int > = arrayOf(6, 12, 18, 30, 36, 42, 48, 54, 60, 66);
val c: Array < Int > = arrayOf(2, 5, 11, 14);
// Note : Here first and last elements
// are not considered as missing.
// Test A
var n: Int = a.count();
task.missingArithmeticPro(a, n);
// Test B
n = b.count();
task.missingArithmeticPro(b, n);
// Test C
n = c.count();
task.missingArithmeticPro(c, n);
}
Output
10
24
8
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment