Longest Geometric Progression

In this article, we have explained how to solve the problem of Longest Geometric Progression efficiently using Dynamic Programming. It involves the use of Map data structure in implementation which is different from other standard problems.

Table of contents:

1. Problem statement: Longest Geometric Progression
2. Naive Approach
3. Dynamic Programming Approach

We can solve it via Naive Approch or via Dynamic Programming (where we have to use Map of Float Map<Float,Integer>).

Problem statement: Longest Geometric Progression

What is a Geometric Progression?

A sequence of elements is a Geometric Progression if it follows the following patterns:

$$a, a * r, a * r^2, a * r^3, ..., a * r^N, ...$$

where:

• a is the first element of the Geometric Progression
• $a * r^{i-1}$ is the i^th element of the Geometric Progression

Let us first take example before solving the problem of Longest Geometric Progression:

A = {2, 4, 8, 10, 50, 250}

So, here we found 2 geometric progressions one of common ratio 2 and other with 5.
Yes, every two number will be in geometric sequence so we are discussing beyond that:

• $a_1$: 2 4 8 , r=2
• $a_2$: 2 10 50 250 , r=5

So, our answer should be 4 (size of a=2).

To better understand this problem we need to observe some properties of geometric progression. Three numbers can be in geometric progression if and only if they hold property:

If a, b, c are in geometric progresion:

$b^2= a * c$
or we can say $b/a = c/b$.

Naive Approach

In Naive Approach, we will follow these steps:

1. First sort the array. It will take $O(N logN)$ time
2. Traverse via a loop starting from first index and then nested one more loop for selecting next element for that progression.
3. Now in inner most loop, we will check for all element which has same common ratio.

Time Complexity: $O(N^3)$

Dynamic Programming Approach

Algorithm

The structure of Dynamic Programming will be:

DP[i][j] = LGP with the first element 
           being array[i] and ratio being j

LGP = Longest Geometric Progression

If there are two elements array[i] and array[j] with ratio R and there is no common ratio as compared to previous element pairs, then:

DP[i][R] = 1

Else if there is common ratio R among previous elements, then:

DP[i][r] = DP[j][r] + 1

Answer is the maximum value in the matrix DP[][].

To implement this technique efficiently with minimum space, you need to use a Map data structure.

Steps to find Longest Geometric Progression using Dynamic Programming:

1. First sort all elements, so we can easily track number of elements which has same common ratio.
2. Intialize an array of type (map<double,int>), length of array would be size of given set.
3. Use two loops one for traversing our set and other for checking out which elements have same common ratio as previous ones. If we can find same common ratio then increment it with via 1, otherwise create a new entity for that map with common ratio and intialize it with two.

Step by step

A = {5, 10, 20, 30}

So size of array,
int n=A.size()

We will declare an array of map type,which store the no of element which made a progression with a common ratio (r).

Now, how we think to solve this problem using dynamic programming,we have to maintain a list of map<float,integer> for every index of an array.

Let us trace the index of all array.

• Element at first index: 5
  There is no element before this index so just continue
• Element at second index: 10

Before 10, we have an element at first index so common ratio r=10/5. With r=2, we update our map at second index list(2)(r) = 2.

• Element at third index: 20

Before this, we have two elements at first and second index. One with common ratio 2 and other we 4. With this, we update values as follows:

list(3)(2) = list(2)(2) + 1 = 3
list(3)(4) = 2

• Element at fourth index: 30

Here we got element with common ratio which has not come before.

list(4)(3/2) = 2
list(4)(3) = 2
list(4)(6) = 2

So, maximum value find at list(3)(2)=3

Answer = 3

PseudoCode

1: Declare map of float as a map value and Integer as a key Value
Map<Float,Integer>dp
2: Now iterate from first index to last index and then put all values with
common ratio in map and increment them
First check the size of given array
let n be size of the array
if(n<=2) then simply n is our answer
otherwise we have to declare an map of same size of array
Map<Float,Integer>dp(n)

   loop(i=0 to n)
   {
    loop (j=0 to less than i)
    {
      float r=A[i]/A[j]
      Search r in dp[j]
        if r is present in dp[j] then 
         dp[i][r] = dp[j][r] + 1  , because we found one more value which has 
         same common 
         ratio.
        else
        Create an map with defaul value 2
        dp[i][r] =2 ,
       }
   }

Now we will discuss about it's various time and space compexities ...

Complexity

• Worst case time complexity: Θ(n^2)
• Average case time complexity: Θ(n^2)
• Best case time complexity: Θ(n^2)
• Space complexity: Θ(n^2)

Implemtation :

int findLargestSequence(int A[])
{
int n=sizeof(A)/sizeof(A[0]);
if(n<=2)
    return n;
sort(A,A+n); //first sort all the elements
map<float,int>dp[n]; // declare  a dp array of size n.
int max=0;

for(int i=0;i<n;i++)
{
    for(int j=0;j<i;j++)
    {
        float r=A[i]/A[j];
        if(dp[j].find(r)!=dp[j].end());
        {
            dp[i].insert(make_pair(r,2));
            //sequence has at least two elements with a ratio(r)
        }
        else
        {
            dp[i][r]=dp[j][r]+1;  
            // if at the jth index we already have a sequence with common ratio r
        }
        if(dp[i][r]>max)
            max=dp[i][r];
    }
}
return max;
}

Time & Space Complexity

Time Complexity: $O(N^2)$
Space Comlexity: $O(N^2)$

Key Points

1: We must have to map of float values because common ratio can be a float or decimal no both.
2: We have to sort the array.

With this article at OpenGenus, you must have the complete idea of Longest Geometric Progression.