Encuentra el número que falta en Progresión Geométrica

Dada una array que representa elementos de progresión geométrica en orden. Falta un elemento en la progresión, encuentra el número que falta. Se puede suponer que siempre falta un término y que el término faltante no es el primero ni el último de la serie.

Ejemplos: 

Input : arr[] = {1, 3 , 27, 81}
Output : 9

Input : arr[] = {4, 16, 64, 1024};
Output : 256

Una solución simple es atravesar linealmente la array y encontrar el número que falta. La complejidad temporal de esta solución es O(n).

Una solución eficiente para resolver este problema en tiempo O (Log n) utilizando la búsqueda binaria. La idea es ir al elemento medio. Compruebe si la relación entre el medio y el próximo al medio es igual o no a la relación común; de lo contrario, el elemento que falta se encuentra entre el medio y el medio+1. Si el elemento del medio es igual al término n/2 en la serie geométrica (sea n el número de elementos en la array de entrada), entonces el elemento faltante se encuentra en la mitad derecha. El elemento Else se encuentra en la mitad izquierda.

Implementación:

// C++ program to find missing number in
// geometric progression
#include <bits/stdc++.h>
using namespace std;
 
// It returns INT_MAX in case of error
int findMissingRec(int arr[], int low,
                   int high, int ratio)
{
    if (low >= high)
        return INT_MAX;
    int mid = low + (high - low)/2;
 
    // If element next to mid is missing
    if (arr[mid+1]/arr[mid] != ratio)
        return (arr[mid] * ratio);
 
    // If element previous to mid is missing
    if ((mid > 0) && (arr[mid]/arr[mid-1]) != ratio)
        return (arr[mid-1] * ratio);
 
    // If missing element is in right half
    if (arr[mid] == arr[0] * (pow(ratio, mid)) )
        return findMissingRec(arr, mid+1, high, ratio);
 
    return findMissingRec(arr, low, mid-1, ratio);
}
 
// Find ration and calls findMissingRec
int findMissing(int arr[], int n)
{
    // Finding ration assuming that the missing term is
    // not first or last term of series.
    int ratio = (float) pow(arr[n-1]/arr[0], 1.0/n);
 
    return findMissingRec(arr, 0, n-1, ratio);
}
 
// Driver code
int main(void)
{
    int arr[] = {2, 4, 8, 32};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << findMissing(arr, n);
    return 0;
}

// JAVA Code for Find the missing number
// in Geometric Progression
class GFG {
      
    // It returns INT_MAX in case of error
    public static int findMissingRec(int arr[], int low,
                       int high, int ratio)
    {
        if (low >= high)
            return Integer.MAX_VALUE;
        int mid = low + (high - low)/2;
      
        // If element next to mid is missing
        if (arr[mid+1]/arr[mid] != ratio)
            return (arr[mid] * ratio);
      
        // If element previous to mid is missing
        if ((mid > 0) && (arr[mid]/arr[mid-1]) != ratio)
            return (arr[mid-1] * ratio);
      
        // If missing element is in right half
        if (arr[mid] == arr[0] * (Math.pow(ratio, mid)) )
            return findMissingRec(arr, mid+1, high, ratio);
      
        return findMissingRec(arr, low, mid-1, ratio);
    }
      
    // Find ration and calls findMissingRec
    public static int findMissing(int arr[], int n)
    {
        // Finding ration assuming that the missing
        // term is not first or last term of series.
        int ratio =(int) Math.pow(arr[n-1]/arr[0], 1.0/n);
      
        return findMissingRec(arr, 0, n-1, ratio);
    }   
     
    /* Driver program to test above function */
    public static void main(String[] args)
    {
        int arr[] = {2, 4, 8, 32};
        int n = arr.length;
         
        System.out.print(findMissing(arr, n));
    }
  }
// This code is contributed by Arnav Kr. Mandal.

# Python3 program to find missing
# number in geometric progression
 
# It returns INT_MAX in case of error
def findMissingRec(arr, low, high, ratio):
 
    if (low >= high):
        return 2147483647
    mid = low + (high - low) // 2
 
    # If element next to mid is missing
    if (arr[mid + 1] // arr[mid] != ratio):
        return (arr[mid] * ratio)
 
    # If element previous to mid is missing
    if ((mid > 0) and (arr[mid] / arr[mid-1]) != ratio):
        return (arr[mid - 1] * ratio)
 
    # If missing element is in right half
    if (arr[mid] == arr[0] * (pow(ratio, mid)) ):
        return findMissingRec(arr, mid+1, high, ratio)
 
    return findMissingRec(arr, low, mid-1, ratio)
 
 
# Find ration and calls findMissingRec
def findMissing(arr, n):
  
    # Finding ration assuming that
    # the missing term is not first
    # or last term of series.
    ratio = int(pow(arr[n-1] / arr[0], 1.0 / n))
 
    return findMissingRec(arr, 0, n-1, ratio)
 
# Driver code
arr = [2, 4, 8, 32]
n = len(arr)
print(findMissing(arr, n))
 
# This code is contributed by Anant Agarwal.

// C# Code for Find the missing number
// in Geometric Progression
using System;
 
class GFG {
     
    // It returns INT_MAX in case of error
    public static int findMissingRec(int []arr, int low,
                                    int high, int ratio)
    {
        if (low >= high)
            return int.MaxValue;
             
        int mid = low + (high - low)/2;
     
        // If element next to mid is missing
        if (arr[mid+1]/arr[mid] != ratio)
            return (arr[mid] * ratio);
     
        // If element previous to mid is missing
        if ((mid > 0) && (arr[mid]/arr[mid-1]) != ratio)
            return (arr[mid-1] * ratio);
     
        // If missing element is in right half
        if (arr[mid] == arr[0] * (Math.Pow(ratio, mid)) )
            return findMissingRec(arr, mid+1, high, ratio);
     
        return findMissingRec(arr, low, mid-1, ratio);
    }
     
    // Find ration and calls findMissingRec
    public static int findMissing(int []arr, int n)
    {
         
        // Finding ration assuming that the missing
        // term is not first or last term of series.
        int ratio =(int) Math.Pow(arr[n-1]/arr[0], 1.0/n);
     
        return findMissingRec(arr, 0, n-1, ratio);
    }
     
    /* Driver program to test above function */
    public static void Main()
    {
        int []arr = {2, 4, 8, 32};
        int n = arr.Length;
         
        Console.Write(findMissing(arr, n));
    }
}
 
// This code is contributed by nitin mittal.

<?php
// PHP program to find missing number
// in geometric progression
 
// It returns INT_MAX in case of error
function findMissingRec(&$arr, $low,
                         $high, $ratio)
{
    if ($low >= $high)
        return PHP_INT_MAX;
    $mid = $low + intval(($high - $low) / 2);
 
    // If element next to mid is missing
    if ($arr[$mid+1]/$arr[$mid] != $ratio)
        return ($arr[$mid] * $ratio);
 
    // If element previous to mid is missing
    if (($mid > 0) && ($arr[$mid] /
                       $arr[$mid - 1]) != $ratio)
        return ($arr[$mid - 1] * $ratio);
 
    // If missing element is in right half
    if ($arr[$mid] == $arr[0] * (pow($ratio, $mid)))
        return findMissingRec($arr, $mid + 1,
                              $high, $ratio);
 
    return findMissingRec($arr, $low,
                          $mid - 1, $ratio);
}
 
// Find ration and calls findMissingRec
function findMissing(&$arr, $n)
{
    // Finding ration assuming that the missing
    // term is not first or last term of series.
    $ratio = (float) pow($arr[$n - 1] /
                         $arr[0], 1.0 / $n);
 
    return findMissingRec($arr, 0, $n - 1, $ratio);
}
 
// Driver code
$arr = array(2, 4, 8, 32);
$n = sizeof($arr);
echo findMissing($arr, $n);
 
// This code is contributed by ita_c
?>

<script>
 
// Javascript Code for Find the missing number
// in Geometric Progression
     
    // It returns INT_MAX in case of error
    function findMissingRec(arr,low,high,ratio)
    {
        if (low >= high)
            return Integer.MAX_VALUE;
        let mid = Math.floor(low + (high - low)/2);
        
        // If element next to mid is missing
        if (arr[mid+1]/arr[mid] != ratio)
            return (arr[mid] * ratio);
        
        // If element previous to mid is missing
        if ((mid > 0) && (arr[mid]/arr[mid-1]) != ratio)
            return (arr[mid-1] * ratio);
        
        // If missing element is in right half
        if (arr[mid] == arr[0] * (Math.pow(ratio, mid)) )
            return findMissingRec(arr, mid+1, high, ratio);
        
        return findMissingRec(arr, low, mid-1, ratio);
    }
     
     // Find ration and calls findMissingRec
    function findMissing(arr,n)
    {
        // Finding ration assuming that the missing
        // term is not first or last term of series.
        let ratio =Math.floor( Math.pow(arr[n-1]/arr[0], 1.0/n));
        
        return findMissingRec(arr, 0, n-1, ratio);
    }
     
    /* Driver program to test above function */
    let arr=[2, 4, 8, 32];
    let n = arr.length;
    document.write(findMissing(arr, n));
     
    // This code is contributed by rag2127
     
</script>

16

Nota: Los inconvenientes de esta solución son: para valores más grandes o para una array más grande, puede causar un desbordamiento y/o puede tomar más tiempo para la potencia de la computadora.

Este artículo es una contribución de Yasin Zafar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.