Encuentra el número que falta en la progresión aritmética

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *