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++
// 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
// 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
# 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#
// 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
// 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
?>
Javascript
<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>
Producción
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.
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