logo

Geometrik İlerlemede eksik sayıyı bulun

Sırayla geometrik ilerlemenin elemanlarını temsil eden bir dizi verilmiştir. İlerlemede bir öğe eksik eksik sayıyı bulun. Bir terimin her zaman eksik olduğu ve eksik terimin serinin ilk veya sonuncusu olmadığı varsayılabilir.

Örnekler:  

Input : arr[] = {1 3  27 81} Output : 9 Input : arr[] = {4 16 64 1024}; Output : 256

A Basit Çözüm diziyi doğrusal olarak geçmek ve eksik sayıyı bulmaktır. Bu çözümün zaman karmaşıklığı O(n)'dir.



bahar ve bahar mvc

Bir verimli çözüm Bu sorunu İkili Aramayı kullanarak O(Log n) sürede çözmek için. Fikir orta elemente gitmektir. Orta ile ortanın yanındakinin oranının ortak orana eşit olup olmadığını kontrol edin, değilse eksik öğe orta ile orta+1 arasında yer alır. Geometrik Seride ortadaki eleman n/2. terime eşitse (giriş dizisindeki eleman sayısı n olsun) eksik eleman sağ yarıdadır. Başka bir öğe sol yarıda yer alır.

Uygulama:

C++
// C++ program to find missing number in // geometric progression #include    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 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(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>  

Çıkış
16

Zaman Karmaşıklığı: O(giriş)

Yardımcı Alan: O(giriş)

Not : Bu çözümün dezavantajları şunlardır: Daha büyük değerler veya daha büyük diziler için taşmaya neden olabilir ve/veya bilgisayarın güçlenmesi daha fazla zaman alabilir.

Java'da tarihi biçimlendir

 

Test Oluştur