Duotas masyvas, vaizduojantis geometrinės progresijos elementus eilės tvarka. Trūksta vieno elemento eigoje, suraskite trūkstamą skaičių. Galima daryti prielaidą, kad vieno termino visada trūksta, o trūkstamas terminas nėra pirmas ar paskutinis iš serijos.
Pavyzdžiai:
Input : arr[] = {1 3 27 81} Output : 9 Input : arr[] = {4 16 64 1024}; Output : 256 A Paprastas Sprendimas yra tiesiškai pereiti masyvą ir rasti trūkstamą skaičių. Šio sprendimo laiko sudėtingumas yra O(n).
skaičiuojant kadenciją „Excel“.
An efektyvus sprendimas Norėdami išspręsti šią problemą per O (Log n) laiką, naudodami dvejetainę paiešką. Idėja yra pereiti prie vidurinio elemento. Patikrinkite, ar vidurio ir šalia vidurio santykis yra lygus bendrajam santykiui, ar ne, jei ne, trūkstamas elementas yra tarp vidurio ir vidurio +1. Jei vidurinis elementas yra lygus n/2-ajam geometrinės serijos nariui (tegul n yra elementų skaičius įvesties masyve), tada trūkstamas elementas yra dešinėje pusėje. Kitas elementas yra kairėje pusėje.
Įgyvendinimas:
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>
Išvestis
16
Laiko sudėtingumas: O (prisijungti)
Pagalbinė erdvė: O (prisijungti)
Pastaba: Šio sprendimo trūkumai yra šie: esant didesnėms reikšmėms arba didesniam masyvui, tai gali sukelti perpildymą ir (arba) gali užtrukti daugiau laiko, kol kompiuteris paleidžiamas.
JAV miestų pavadinimai
Sukurti viktoriną