Dado um array que representa elementos de progressão geométrica em ordem. Um elemento está faltando na progressão, encontre o número que falta. Pode-se presumir que sempre falta um termo e que o termo faltante não é o primeiro nem o último da série.
Exemplos:
Input : arr[] = {1 3 27 81} Output : 9 Input : arr[] = {4 16 64 1024}; Output : 256 UM Solução Simples é percorrer linearmente a matriz e encontrar o número que falta. A complexidade de tempo desta solução é O(n).
como converter de int para string em java
Um solução eficiente para resolver este problema em tempo O (Log n) usando Pesquisa Binária. A ideia é ir para o elemento intermediário. Verifique se a proporção do meio e próximo ao meio é igual à proporção comum ou não, caso contrário, o elemento que falta está entre o meio e o meio + 1. Se o elemento do meio for igual ao n/2º termo na série geométrica (seja n o número de elementos na matriz de entrada), então o elemento ausente estará na metade direita. O outro elemento está na metade esquerda.
Implementação:
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>
Saída
16
Complexidade de tempo: O(logn)
Espaço Auxiliar: O(logn)
Observação : As desvantagens desta solução são: Para valores maiores ou para matrizes maiores, pode causar estouro e/ou levar mais tempo para a alimentação do computador.
contar distinto
Criar questionário