Dada una array que representa elementos de progresión aritmética en orden. Falta un elemento en la progresión, encuentra el número que falta.
Ejemplos:
C++
// C++ program to find the missing number
// in a given arithmetic progression
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int findMissing(int arr[], int n)
{
int a,d,l,s,i,sum=0,missingnumber;
a=arr[0];
l=arr[n-1];
/* Taking the sum of all the elements of the array
including the missing element using formulae
S(n) = n/2 (a+l) where a is the first element
and l is the last element */
if((a+l)%2==0) /* ensuring this as n/2(a+l) and (a+l)/2
would give different values programmatically */
{
s = (a+l)/2;
s = s*(n+1);
}
else
{
s = (n+1)/2;
s = (a+l)*s;
}
// Taking the sum of all the elements of the
// array excluding the missing element
for(i=0;i<=n-1;i++)
{
sum = sum + arr[i];
}
missingnumber=s-sum;
return missingnumber;
}
// Driver Code
int main()
{
int arr[] = {2, 4, 8, 10, 12, 14};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The missing element is "
<< findMissing(arr, n);
return 0;
}
// This code is contributed by Aditya Dudhane
Java
// Java program to find the missing number
// in a given arithmetic progression
class GFG {
static int findMissing(int[] arr, int n)
{
int a, l, s, i, sum = 0, missingnumber;
a = arr[0];
l = arr[n - 1];
/* Taking the sum of all the elements of the array
including the missing element using formulae
S(n) = n/2 (a+l) where a is the first element
and l is the last element */
if ((a + l) % 2 == 0) /* ensuring this as n/2(a+l)
and (a+l)/2 would give different values
programmatically */
{
s = (a + l) / 2;
s = s * (n + 1);
}
else {
s = (n + 1) / 2;
s = (a + l) * s;
}
// Taking the sum of all the elements of the
// array excluding the missing element
for (i = 0; i <= n - 1; i++) {
sum = sum + arr[i];
}
missingnumber = s - sum;
return missingnumber;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 2, 4, 8, 10, 12, 14 };
int n = arr.length;
System.out.println("The missing element is "
+ findMissing(arr, n));
}
}
// This code is contributed by phasing17
Python3
# Python program to find the missing number # in a given arithmetic progression # Function to find the missing number def find_missing(arr, n): first = arr[0] last = arr[-1] # Explained above if (first + last) % 2: s = (n + 1) / 2 s *= (first + last) else: s = (first + last) / 2 s *= (n + 1) missing = s - sum(arr) return missing # Driver Code if __name__ == "__main__": arr = [2, 4, 8, 10, 12, 14] n = len(arr) missing = find_missing(arr, n) print(missing) # This code is contributed by kraanzu.
C#
// C# program to find the missing number
// in a given arithmetic progression
using System;
class GFG {
static int findMissing(int[] arr, int n)
{
int a, l, s, i, sum = 0, missingnumber;
a = arr[0];
l = arr[n - 1];
/* Taking the sum of all the elements of the array
including the missing element using formulae
S(n) = n/2 (a+l) where a is the first element
and l is the last element */
if ((a + l) % 2
== 0) /* ensuring this as n/2(a+l) and (a+l)/2
would give different values
programmatically */
{
s = (a + l) / 2;
s = s * (n + 1);
}
else {
s = (n + 1) / 2;
s = (a + l) * s;
}
// Taking the sum of all the elements of the
// array excluding the missing element
for (i = 0; i <= n - 1; i++) {
sum = sum + arr[i];
}
missingnumber = s - sum;
return missingnumber;
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 2, 4, 8, 10, 12, 14 };
int n = arr.Length;
Console.Write("The missing element is "
+ findMissing(arr, n));
}
}
// This code is contributed by phasing17
Javascript
// JavaScript program to find the missing number
// in a given arithmetic progression
function findMissing(arr, n)
{
let a, d, l, s, i, sum = 0, missingnumber;
a = arr[0];
l = arr[n - 1];
/* Taking the sum of all the elements of the array
including the missing element using formulae
S(n) = n/2 (a+l) where a is the first element
and l is the last element */
if((a+l)%2==0) /* ensuring this as n/2(a+l) and (a+l)/2
would give different values programmatically */
{
s = (a+l)/2;
s = s*(n+1);
}
else
{
s = (n+1)/2;
s = (a+l)*s;
}
// Taking the sum of all the elements of the
// array excluding the missing element
for(i = 0; i <= n - 1; i++)
{
sum = sum + arr[i];
}
missingnumber = s - sum;
return missingnumber;
}
// Driver Code
let arr = [2, 4, 8, 10, 12, 14];
let n =arr.length;
console.log("The missing element is", findMissing(arr, n));
// This code is contributed by phasing17
C++
// C++ program to find the missing number
// in a given arithmetic progression
#include<iostream>
using namespace std;
#define INT_MAX 2147483647;
class GFG
{
// A binary search based recursive function that returns
// the missing element in arithmetic progression
public:int findMissingUtil(int arr[], int low,
int high, int diff)
{
// There must be two elements to find the missing
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);
}
// The function uses findMissingUtil() to
// find the missing element in AP.
// It assumes that there is exactly one
// missing element and may give incorrect result
// when there is no missing element or
// more than one missing elements. This function
// also assumes that the difference in AP is an
// integer.
int findMissing(int arr[], int n)
{
// If exactly one element is missing, then we can find
// difference of arithmetic progression using following
// formula. Example, 2, 4, 6, 10, diff = (10-2)/4 = 2.
// The assumption in formula is that the difference is
// an integer.
int diff = (arr[n - 1] - arr[0]) / n;
// Binary search for the missing
// number using above calculated diff
return findMissingUtil(arr, 0, n - 1, diff);
}
};
// Driver Code
int main()
{
GFG g;
int arr[] = {2, 4, 8, 10, 12, 14};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The missing element is "
<< g.findMissing(arr, n);
return 0;
}
// This code is contributed by Soumik
C
// A C program to find the missing number in a given
// arithmetic progression
#include <stdio.h>
#include <limits.h>
// A binary search based recursive function that returns
// the missing element in arithmetic progression
int findMissingUtil(int arr[], int low, int high, int diff)
{
// There must be two elements to find the missing
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);
}
// The function uses findMissingUtil() to find the missing
// element in AP. It assumes that there is exactly one missing
// element and may give incorrect result when there is no missing
// element or more than one missing elements.
// This function also assumes that the difference in AP is an
// integer.
int findMissing(int arr[], int n)
{
// If exactly one element is missing, then we can find
// difference of arithmetic progression using following
// formula. Example, 2, 4, 6, 10, diff = (10-2)/4 = 2.
// The assumption in formula is that the difference is
// an integer.
int diff = (arr[n-1] - arr[0])/n;
// Binary search for the missing number using above
// calculated diff
return findMissingUtil(arr, 0, n-1, diff);
}
/* Driver program to check above functions */
int main()
{
int arr[] = {2, 4, 8, 10, 12, 14};
int n = sizeof(arr)/sizeof(arr[0]);
printf("The missing element is %d", findMissing(arr, n));
return 0;
}
Java
// A Java program to find
// the missing number in
// a given arithmetic
// progression
import java.io.*;
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 Integer.MAX_VALUE;
// 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);
}
// The function uses findMissingUtil()
// to find the missing element in AP.
// It assumes that there is exactly
// one missing element and may give
// incorrect result when there is no
// missing element or more than one
// missing elements. This function also
// assumes that the difference in AP is
// an integer.
static int findMissing(int arr[], int n)
{
// If exactly one element is missing,
// then we can find difference of
// arithmetic progression using
// following formula. Example, 2, 4,
// 6, 10, diff = (10-2)/4 = 2.
// The assumption in formula is that
// the difference is an integer.
int diff = (arr[n - 1] - arr[0]) / n;
// Binary search for the missing
// number using above calculated diff
return findMissingUtil(arr, 0, n - 1, diff);
}
// Driver Code
public static void main (String[] args)
{
int arr[] = {2, 4, 8, 10, 12, 14};
int n = arr.length;
System.out.println("The missing element is "+
findMissing(arr, n));
}
}
// This code is contributed by anuj_67.
Python3
# 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):
# There must be two elements to
# find the missing
if (high <= low):
return sys.maxsize;
# Find index of middle element
mid = int(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 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);
# The function uses findMissingUtil() to find
# the missing element in AP. It assumes that
# there is exactly one missing element and may
# give incorrect result when there is no missing
# element or more than one missing elements.
# This function also assumes that the difference
# in AP is an integer.
def findMissing(arr, n):
# If exactly one element is missing, then
# we can find difference of arithmetic
# progression using following formula.
# Example, 2, 4, 6, 10, diff = (10-2)/4 = 2.
# The assumption in formula is that the
# difference is an integer.
diff = int((arr[n - 1] - arr[0]) / n);
# Binary search for the missing number
# using above calculated diff
return findMissingUtil(arr, 0, n - 1, diff);
# Driver Code
arr = [2, 4, 8, 10, 12, 14];
n = len(arr);
print("The missing element is",
findMissing(arr, n));
# This code is contributed by chandan_jnu
C#
// 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.
// 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);
}
// The function uses findMissingUtil()
// to find the missing element
// in AP. It assumes that there
// is exactly one missing element
// and may give incorrect result
// when there is no missing element
// or more than one missing elements.
// This function also assumes that
// the difference in AP is an integer.
static int findMissing(int []arr, int n)
{
// If exactly one element
// is missing, then we can
// find difference of arithmetic
// progression using following
// formula. Example, 2, 4, 6, 10,
// diff = (10-2)/4 = 2.The assumption
// in formula is that the difference
// is an integer.
int diff = (arr[n - 1] -
arr[0]) / n;
// Binary search for the
// missing number using
// above calculated diff
return findMissingUtil(arr, 0,
n - 1, diff);
}
// Driver Code
public static void Main ()
{
int []arr = {2, 4, 8,
10, 12, 14};
int n = arr.Length;
Console.WriteLine("The missing element is "+
findMissing(arr, n));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// A PHP 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 PHP_INT_MAX;
// Find index of middle element
$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);
}
// The function uses findMissingUtil() to find
// the missing element in AP. It assumes that
// there is exactly one missing element and may
// give incorrect result when there is no missing
// element or more than one missing elements.
// This function also assumes that the difference
// in AP is an integer.
function findMissing($arr, $n)
{
// If exactly one element is missing, then
// we can find difference of arithmetic
// progression using following formula.
// Example, 2, 4, 6, 10, diff = (10-2)/4 = 2.
// The assumption in formula is that the
// difference is an integer.
$diff = ($arr[$n - 1] - $arr[0]) / $n;
// Binary search for the missing number
// using above calculated diff
return findMissingUtil($arr, 0, $n - 1, $diff);
}
// Driver Code
$arr = array(2, 4, 8, 10, 12, 14);
$n = sizeof($arr);
echo "The missing element is ",
findMissing($arr, $n);
// This code is contributed by Sach_Code
?>
Javascript
<script>
// 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 + parseInt((high - low) / 2, 10);
// 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);
}
// The function uses findMissingUtil()
// to find the missing element in AP.
// It assumes that there is exactly
// one missing element and may give
// incorrect result when there is no
// missing element or more than one
// missing elements. This function also
// assumes that the difference in AP is
// an integer.
function findMissing(arr, n)
{
// If exactly one element is missing,
// then we can find difference of
// arithmetic progression using
// following formula. Example, 2, 4,
// 6, 10, diff = (10-2)/4 = 2.
// The assumption in formula is that
// the difference is an integer.
let diff = parseInt((arr[n - 1] - arr[0]) / n, 10);
// Binary search for the missing
// number using above calculated diff
return findMissingUtil(arr, 0, n - 1, diff);
}
let arr = [2, 4, 8, 10, 12, 14];
let n = arr.length;
document.write("The missing element is "+
findMissing(arr, n));
</script>
C++
// C++ program to find the missing number
// in a given arithmetic progression
#include<iostream>
using namespace std;
#define INT_MAX 2147483647;
class GFG
{
// A binary search based function that returns
// the missing element in arithmetic progression
public:int findMissingUtil(int arr[], int low,
int high, int diff)
{
// Find index of middle element
int mid;
while (low <= high)
{
// find index of middle element
mid = (low + high) / 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)
low = mid + 1;
else
// the missing element will exist in left half
high = mid - 1;
}
// after breaking out of binary search loop
// our missing element will exist between high and low
// our missing element will be a[high] + common difference
// or a[low] - common difference
return arr[high] + diff;
}
// The function uses findMissingUtil() to
// find the missing element in AP.
// It assumes that there is exactly one
// missing element and may give incorrect result
// when there is no missing element or
// more than one missing elements. This function
// also assumes that the difference in AP is an
// integer.
int findMissing(int arr[], int n)
{
// If exactly one element is missing, then we can find
// difference of arithmetic progression using following
// formula. Example, 2, 4, 6, 10, diff = (10-2)/4 = 2.
// The assumption in formula is that the difference is
// an integer.
int diff = (arr[n - 1] - arr[0]) / n;
// Binary search for the missing
// number using above calculated diff
return findMissingUtil(arr, 0, n - 1, diff);
}
};
// Driver Code
int main()
{
GFG g;
int arr[] = {2, 4, 8, 10, 12, 14};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The missing element is "
<< g.findMissing(arr, n);
return 0;
}
// This code is contributed by gurudev620gs
C
// A C program to find the missing number in a given
// arithmetic progression
#include <stdio.h>
#include <limits.h>
// A binary search based function that returns
// the missing element in arithmetic progression
int findMissingUtil(int arr[], int low, int high, int diff)
{
// Find index of middle element
int mid;
while (low <= high)
{
// find index of middle element
mid = (low + high) / 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)
low = mid + 1;
else
// the missing element will exist in left half
high = mid - 1;
}
// after breaking out of binary search loop
// our missing element will exist between high and low
// our missing element will be a[high] + common difference
// or a[low] - common difference
return arr[high] + diff;
}
// The function uses findMissingUtil() to find the missing
// element in AP. It assumes that there is exactly one missing
// element and may give incorrect result when there is no missing
// element or more than one missing elements.
// This function also assumes that the difference in AP is an
// integer.
int findMissing(int arr[], int n)
{
// If exactly one element is missing, then we can find
// difference of arithmetic progression using following
// formula. Example, 2, 4, 6, 10, diff = (10-2)/4 = 2.
// The assumption in formula is that the difference is
// an integer.
int diff = (arr[n-1] - arr[0])/n;
// Binary search for the missing number using above
// calculated diff
return findMissingUtil(arr, 0, n-1, diff);
}
/* Driver program to check above functions */
int main()
{
int arr[] = {2, 4, 8, 10, 12, 14};
int n = sizeof(arr)/sizeof(arr[0]);
printf("The missing element is %d", findMissing(arr, n));
return 0;
}
Java
// A Java program to find
// the missing number in
// a given arithmetic
// progression
import java.io.*;
class GFG
{
// A binary search function that
// returns the missing
// element in arithmetic
// progression
static int findMissingUtil(int arr[], int low,
int high, int diff)
{
// Find index of middle element
int mid;
while (low <= high)
{
// find index of middle element
mid = (low + high) / 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)
low = mid + 1;
else
// the missing element will exist in left half
high = mid - 1;
}
// after breaking out of binary search loop
// our missing element will exist between high and low
// our missing element will be a[high] + common difference
// or a[low] - common difference
return arr[high] + diff;
}
// The function uses findMissingUtil()
// to find the missing element in AP.
// It assumes that there is exactly
// one missing element and may give
// incorrect result when there is no
// missing element or more than one
// missing elements. This function also
// assumes that the difference in AP is
// an integer.
static int findMissing(int arr[], int n)
{
// If exactly one element is missing,
// then we can find difference of
// arithmetic progression using
// following formula. Example, 2, 4,
// 6, 10, diff = (10-2)/4 = 2.
// The assumption in formula is that
// the difference is an integer.
int diff = (arr[n - 1] - arr[0]) / n;
// Binary search for the missing
// number using above calculated diff
return findMissingUtil(arr, 0, n - 1, diff);
}
// Driver Code
public static void main (String[] args)
{
int arr[] = {2, 4, 8, 10, 12, 14};
int n = arr.length;
System.out.println("The missing element is "+
findMissing(arr, n));
}
}
// This code is contributed by gurudev620gs.
Python3
# A Python3 program to find the missing
# number in a given arithmetic progression
import sys
# A binary search based function
# that returns the missing element in
# arithmetic progression
def findMissingUtil(arr, low, high, diff):
while low <= high:
# find index of middle element
mid = (low + high)//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:
low = mid + 1
else:
# the missing element will exist in left half
high = mid - 1
# after breaking out of binary search loop
# our missing element will exist between high and low
# our missing element will be a[high] + common difference
# or a[low] - common difference
return arr[high] + diff
# The function uses findMissingUtil() to find
# the missing element in AP. It assumes that
# there is exactly one missing element and may
# give incorrect result when there is no missing
# element or more than one missing elements.
# This function also assumes that the difference
# in AP is an integer.
def findMissing(arr, n):
# If exactly one element is missing, then
# we can find difference of arithmetic
# progression using following formula.
# Example, 2, 4, 6, 10, diff = (10-2)/4 = 2.
# The assumption in formula is that the
# difference is an integer.
diff = int((arr[n - 1] - arr[0]) / n);
# Binary search for the missing number
# using above calculated diff
return findMissingUtil(arr, 0, n - 1, diff);
# Driver Code
arr = [2, 4, 8, 10, 12, 14];
n = len(arr);
print("The missing element is",
findMissing(arr, n));
# This code is contributed by gurudev620gs
C#
// A C# program to find
// the missing number in
// a given arithmetic
// progression
using System;
class GFG
{
// A binary search function that
// returns the missing
// element in arithmetic
// progression
static int findMissingUtil(int []arr, int low,
int high, int diff)
{
// Find index of middle element
int mid;
while (low <= high)
{
// find index of middle element
mid = (low + high) / 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)
low = mid + 1;
else
// the missing element will exist in left half
high = mid - 1;
}
// after breaking out of binary search loop
// our missing element will exist between high and low
// our missing element will be a[high] + common difference
// or a[low] - common difference
return arr[high] + diff;
}
// The function uses findMissingUtil()
// to find the missing element
// in AP. It assumes that there
// is exactly one missing element
// and may give incorrect result
// when there is no missing element
// or more than one missing elements.
// This function also assumes that
// the difference in AP is an integer.
static int findMissing(int []arr, int n)
{
// If exactly one element
// is missing, then we can
// find difference of arithmetic
// progression using following
// formula. Example, 2, 4, 6, 10,
// diff = (10-2)/4 = 2.The assumption
// in formula is that the difference
// is an integer.
int diff = (arr[n - 1] -
arr[0]) / n;
// Binary search for the
// missing number using
// above calculated diff
return findMissingUtil(arr, 0,
n - 1, diff);
}
// Driver Code
public static void Main ()
{
int []arr = {2, 4, 8,
10, 12, 14};
int n = arr.Length;
Console.WriteLine("The missing element is "+
findMissing(arr, n));
}
}
// This code is contributed by gurudev620gs.
PHP
<?php
// A PHP program to find the missing
// number in a given arithmetic progression
// A binary search based function
// that returns the missing element in
// arithmetic progression
function findMissingUtil($arr, $low, $high, $diff)
{
while ($low <= $high)
{
// find index of middle element
$mid = ($low + $high) / 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)
$low = $mid + 1;
else
// the missing element will exist in left half
$high = $mid - 1;
}
// after breaking out of binary search loop
// our missing element will exist between high and low
// our missing element will be a[high] + common difference
// or a[low] - common difference
return $arr[$high] + $diff;
}
// The function uses findMissingUtil() to find
// the missing element in AP. It assumes that
// there is exactly one missing element and may
// give incorrect result when there is no missing
// element or more than one missing elements.
// This function also assumes that the difference
// in AP is an integer.
function findMissing($arr, $n)
{
// If exactly one element is missing, then
// we can find difference of arithmetic
// progression using following formula.
// Example, 2, 4, 6, 10, diff = (10-2)/4 = 2.
// The assumption in formula is that the
// difference is an integer.
$diff = ($arr[$n - 1] - $arr[0]) / $n;
// Binary search for the missing number
// using above calculated diff
return findMissingUtil($arr, 0, $n - 1, $diff);
}
// Driver Code
$arr = array(2, 4, 8, 10, 12, 14);
$n = sizeof($arr);
echo "The missing element is ",
findMissing($arr, $n);
// This code is contributed by gurudev620.gs
?>
Javascript
<script>
// A JavaScript program to find
// the missing number in
// a given arithmetic
// progression
// A binary search function that
// returns the missing
// element in arithmetic
// progression
function findMissingUtil(arr, low, high, diff)
{
// Find index of middle element
int mid;
while (low <= high)
{
// find index of middle element
mid = (low + high) / 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)
low = mid + 1;
else
// the missing element will exist in left half
high = mid - 1;
}
// after breaking out of binary search loop
// our missing element will exist between high and low
// our missing element will be a[high] + common difference
// or a[low] - common difference
return arr[high] + diff;
}
// The function uses findMissingUtil()
// to find the missing element in AP.
// It assumes that there is exactly
// one missing element and may give
// incorrect result when there is no
// missing element or more than one
// missing elements. This function also
// assumes that the difference in AP is
// an integer.
function findMissing(arr, n)
{
// If exactly one element is missing,
// then we can find difference of
// arithmetic progression using
// following formula. Example, 2, 4,
// 6, 10, diff = (10-2)/4 = 2.
// The assumption in formula is that
// the difference is an integer.
let diff = parseInt((arr[n - 1] - arr[0]) / n, 10);
// Binary search for the missing
// number using above calculated diff
return findMissingUtil(arr, 0, n - 1, diff);
}
let arr = [2, 4, 8, 10, 12, 14];
let n = arr.length;
document.write("The missing element is "+
findMissing(arr, n));
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA