Dada una matriz 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 que falta 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 A Solución sencilla es recorrer linealmente la matriz y encontrar el número que falta. La complejidad temporal de esta solución es O (n).
comando de linea de autocad
Un solución eficiente para resolver este problema en tiempo O (Log n) usando la búsqueda binaria. La idea es ir al elemento medio. Compruebe si la proporción entre el medio y el siguiente al medio es igual a la proporción común o no; de lo contrario, el elemento que falta se encuentra entre el medio y el medio+1. Si el elemento del medio es igual a n/2º término en la serie geométrica (sea n el número de elementos en la matriz de entrada), entonces el elemento que falta se encuentra en la mitad derecha. El resto del elemento se encuentra en la mitad izquierda.
Implementación:
C++// C++ program to find missing number in // geometric progression #include
// 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 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(arrlowhighratio) { 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(arrn) { // 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
Complejidad del tiempo: O(iniciar sesión)
Espacio Auxiliar: O(iniciar sesión)
Nota : El inconveniente de esta solución es: para valores más grandes o para una matriz más grande, puede causar desbordamiento y/o puede tomar más tiempo para que la computadora se encienda.
diferencia entre hielo y nieve
Crear cuestionario