How to find the missing number in Geometric Progression in Python

So, guys today we will learn How to find the missing number in Geometric Progression in Python. Let’s do it together. We are basically supposed to find the number which is missing in GP. GP will be given the form of an array. GP is a progression of numbers with a constant ratio between each number and the one before.

You Guys may find it a bit difficult but don’t worry it’s too easy, let’s dive deep into the code.

Finding the missing number in Geometric Progression in Python

We can find the missing element by literally traversing the array. It is one the simplest solution for which time complexity is O(N)

Another way of finding the missing number is by the binary search method. This is also simple but just the difference that time complexity changes that is  O(logN)

E.g

Sample : A[] = {1, 5 , 125, 625}

Ans : 25

Sample : B[] = {3, 9, 81, 243}

Ans : 27

Code:

def noMissed(sample, l, h, ratio): 

  if (l >= h): 
    return 2147483647
  m = l + (h - l) // 2


  if (sample[m + 1] // sample[m] != ratio): 
    return (sample[m] * ratio) 

  
  if ((m > 0) and (sample[m] / sample[m-1]) != ratio): 
    return (sample[m - 1] * ratio) 


  if (sample[m] == sample[0] * (pow(ratio, m)) ): 
    return noMissed(sample, m+1, h, ratio) 

  return noMissed(sample, l, m-1, ratio) 


 
def find(sample, length): 

 
  ratio = int(pow(sample[length-1] / sample[0], 1.0 / length)) 

  return noMissed(sample, 0, length-1, ratio) 

 
sample = [3, 9, 81, 243] 
length = len(sample) 
ans=str(find(sample, length))
print("Missing Number in GP is " +ans) 

Output:

Missing Number in GP is 27

Want to learn more! Have a look at some more amazing pieces of codes..!

 

What is Anagram Substring Search? Explain using program in Python

How to implement Navie String Searching Algorithm in Python

Leave a Reply

Your email address will not be published.