Tutorialspoint.dev

Longest Geometric Progression

Given a set of numbers, find the Length of the Longest Geometrix Progression (LLGP) in it. The common ratio of GP must be an integer.

Examples:

set[] = {5, 7, 10, 15, 20, 29}
output = 3
The longest arithmetic progression is {5, 10, 20}

set[] = {3, 9, 27, 81}
output = 4


This problem is similar to Longest Arithmetic Progression Problem. We can solve this problem using Dynamic Programming.

We first sort the given set. We use an auxiliary table L[n][n] to store results of subproblems. An entry L[i][j] in this table stores LLGP with set[i] and set[j] as first two elements of GP and j > i. The table is filled from bottom right to top left. To fill the table, j (second element in GP) is first fixed. i and k are searched for a fixed j. If i and k are found such that i, j, k form an GP, then the value of L[i][j] is set as L[j][k] + 1. Note that the value of L[j][k] must have been filled before as the loop traverses from right to left columns.

Following is implementation of the Dynamic Programming algorithm.

C++



// C++ program to find length of the longest geometric
// progression in a given set
#include <iostream>
#include <algorithm>
using namespace std;
  
// Returns length of the longest GP subset of set[]
int lenOfLongestGP(int set[], int n)
{
    // Base cases
    if (n < 2)
        return n;
    if (n == 2)
        return (set[1] % set[0] == 0);
  
    // Let us sort the set first
    sort(set, set+n);
  
    // An entry L[i][j] in this table stores LLGP with
    // set[i] and set[j] as first two elements of GP
    // and j > i.
    int L[n][n];
  
    // Initialize result (A single element is always a GP)
    int llgp = 1;
  
    // Initialize values of last column
    for (int i = 0; i < n; ++i)
        if (set[n-1] % set[i] == 0)
            L[i][n-1] = 2;
        else
            L[i][n-1] = 1;
  
  
    // Consider every element as second element of GP
    for (int j = n - 2; j >= 1; --j)
    {
        // Search for i and k for j
        int i = j - 1, k = j+1;
        while (i>=0 && k <= n-1)
        {
            // Two cases when i, j and k don't form
            // a GP.
            if (set[i] * set[k] < set[j]*set[j])
                ++k;
  
            else if (set[i] * set[k] > set[j]*set[j])
            {
                if (set[j] % set[i] == 0)
                    L[i][j] = 2;
                else
                    L[i][j] = 1;
                --i;
            }
  
  
            // i, j and k form GP, LLGP with i and j as
            // first two elements is equal to LLGP with
            // j and k as first two elements plus 1.
            // L[j][k] must have been filled before as
            // we run the loop from right side
            else
            {
                L[i][j] = L[j][k] + 1;
  
                // Update overall LLGP
                if (L[i][j] > llgp)
                    llgp = L[i][j];
  
  
                // Change i and k to fill more L[i][j]
                // values for current j
                --i;
                ++k;
            }
        }
  
        // If the loop was stopped due to k becoming
        // more than n-1, set the remaining entties
        // in column j as 1 or 2 based on divisibility
        // of set[j] by set[i]
        while (i >= 0)
        {
            if (set[j] % set[i] == 0)
                L[i][j] = 2;
            else
                L[i][j] = 1;
            --i;
        }
    }
  
    // Return result
    return llgp;
}
  
// Driver code
int main()
{
    int set1[] = {1, 3, 9, 27, 81, 243};
    int n1 = sizeof(set1)/sizeof(set1[0]);
    cout << lenOfLongestGP(set1, n1) << " ";
  
    int set2[] = {1, 3, 4, 9, 7, 27};
    int n2 = sizeof(set2)/sizeof(set2[0]);
    cout << lenOfLongestGP(set2, n2) << " ";
  
    int set3[] = {2, 3, 5, 7, 11, 13};
    int n3 = sizeof(set3)/sizeof(set3[0]);
    cout << lenOfLongestGP(set3, n3) << " ";
  
    return 0;
}

Java

// Java program to find length 
// of the longest geometric 
// progression in a given set 
import java.util.*;
  
class GFG
{
  
    // Returns length of the longest GP subset of set[] 
    static int lenOfLongestGP(int set[], int n) 
    {
        // Base cases 
        if (n < 2
        {
            return n;
        }
        if (n == 2)
        {
            return (set[1] % set[0] == 0 ? 1 : 0);
        }
  
        // Let us sort the set first 
        Arrays.sort(set);
  
        // An entry L[i][j] in this table 
        // stores LLGP with set[i] and set[j]
        // as first two elements of GP 
        // and j > i. 
        int L[][] = new int[n][n];
  
        // Initialize result (A single 
        // element is always a GP) 
        int llgp = 1;
  
        // Initialize values of last column 
        for (int i = 0; i < n; ++i) 
        {
            if (set[n - 1] % set[i] == 0)
            {
                L[i][n - 1] = 2;
            
            else 
            {
                L[i][n - 1] = 1;
            }
        }
  
        // Consider every element as second element of GP 
        for (int j = n - 2; j >= 1; --j) 
        {
            // Search for i and k for j 
            int i = j - 1, k = j + 1;
            while (i >= 0 && k <= n - 1
            {
                // Two cases when i, j and k 
                // don't form a GP. 
                if (set[i] * set[k] < set[j] * set[j])
                {
                    ++k;
                
                else if (set[i] * set[k] > set[j] * set[j]) 
                {
                    if (set[j] % set[i] == 0
                    {
                        L[i][j] = 2;
                    
                    else 
                    {
                        L[i][j] = 1;
                    }
                    --i;
                
                  
                // i, j and k form GP, LLGP with i and j as 
                // first two elements is equal to LLGP with 
                // j and k as first two elements plus 1. 
                // L[j][k] must have been filled before as 
                // we run the loop from right side 
                else 
                {
                    L[i][j] = L[j][k] + 1;
  
                    // Update overall LLGP 
                    if (L[i][j] > llgp) 
                    {
                        llgp = L[i][j];
                    }
  
                    // Change i and k to fill more L[i][j] 
                    // values for current j 
                    --i;
                    ++k;
                }
            }
  
            // If the loop was stopped due to k becoming 
            // more than n-1, set the remaining entties 
            // in column j as 1 or 2 based on divisibility 
            // of set[j] by set[i] 
            while (i >= 0
            {
                if (set[j] % set[i] == 0
                {
                    L[i][j] = 2;
                
                else 
                {
                    L[i][j] = 1;
                }
                --i;
            }
        }
  
        // Return result 
        return llgp;
    }
  
    // Driver code 
    public static void main(String[] args)
    {
        int set1[] = {1, 3, 9, 27, 81, 243};
        int n1 = set1.length;
        System.out.print(lenOfLongestGP(set1, n1) + " ");
  
        int set2[] = {1, 3, 4, 9, 7, 27};
        int n2 = set2.length;
        System.out.print(lenOfLongestGP(set2, n2) + " ");
  
        int set3[] = {2, 3, 5, 7, 11, 13};
        int n3 = set3.length;
        System.out.print(lenOfLongestGP(set3, n3) + " ");
    }
}
  
/* This code contributed by PrinciRaj1992 */

Python3

# Python3 program to find length of the longest geometric
# progression in a given sett 
  
# Returns length of the longest GP subset of sett[]
def lenOfLongestGP(sett,n):
    # Base cases 
    if n<2:
        return n
    if n==2:
        return (sett[1] % sett[0] == 0)
    # let us sort the sett first 
    sett.sort()
      
    # An entry L[i][j] in this table stores LLGP with 
    # sett[i] and sett[j] as first two elements of GP
    # and j > i.
    L=[[0 for i in range(n)] for i in range(n)]
  
    # Initialize result (A single element is always a GP) 
    llgp=1
  
    # Initialize values of last column 
    for i in range(0,n):
        if sett[n-1] % sett[i] == 0:
            L[i][n-1] = 2
        else:
            L[i][n-1] = 1
              
    # Consider every element as second element of GP 
    for j in range(n-2,0,-1):
          
        # Search for i and k for j 
        i=j-1
        k=j+1
        while i>=0 and k<=n-1:
              
            # Two cases when i, j and k don't form 
            # a GP.
            if sett[i] * sett[k] < sett[j]*sett[j]:
                k+=1
            elif sett[i] * sett[k] > sett[j]*sett[j]:
                if sett[j] % sett[i] == 0:
                    L[i][j]=2
                else:
                    L[i][j]=1
                i-=1
                  
            # i, j and k form GP, LLGP with i and j as 
            # first two elements is equal to LLGP with 
            # j and k as first two elements plus 1.
            # L[j][k] must have been filled before as 
            # we run the loop from right side
            else:
                L[i][j] = L[j][k] + 1
                  
                # Update overall LLGP
                if L[i][j] > llgp:
                    llgp = L[i][j]
                      
                # Change i and k to fill more L[i][j]
                # values for current j 
                i-=1
                k+1
                  
        # If the loop was stopped due to k becoming
        # more than n-1, sett the remaining entties 
        # in column j as 1 or 2 based on divisibility 
        # of sett[j] by sett[i] 
        while i>=0:
            if sett[j] % sett[i] == 0:
                L[i][j]=2
            else:
                L[i][j]=1
            i-=1
    return llgp
# Driver code 
if __name__=='__main__':
    set1=[1, 3, 9, 27, 81, 243]
    n1=len(set1)
    print(lenOfLongestGP(set1,n1))
  
    set2 = [1, 3, 4, 9, 7, 27]
    n2=len(set2)
    print(lenOfLongestGP(set2,n2))
  
    set3 = [2, 3, 5, 7, 11, 13]
    n3=len(set3)
    print(lenOfLongestGP(set3,n3))
  
# this code is contrubuted by sahilshelangia

C#

// C# program to find length 
// of the longest geometric 
// progression in a given Set 
using System;
  
class GFG
{
  
    // Returns length of the 
    // longest GP subset of Set[] 
    static int lenOfLongestGP(int []Set, int n) 
    {
        // Base cases 
        if (n < 2) 
        {
            return n;
        }
        if (n == 2)
        {
            return (Set[1] % Set[0] == 0 ? 1 : 0);
        }
  
        // Let us sort the Set first 
        Array.Sort(Set);
  
        // An entry L[i,j] in this table 
        // stores LLGP with Set[i] and Set[j]
        // as first two elements of GP 
        // and j > i. 
        int [,]L = new int[n, n];
  
        // Initialize result (A single 
        // element is always a GP) 
        int llgp = 1;
  
        // Initialize values of last column 
        for (int i = 0; i < n; ++i) 
        {
            if (Set[n - 1] % Set[i] == 0)
            {
                L[i, n - 1] = 2;
            
            else
            {
                L[i, n - 1] = 1;
            }
        }
  
        // Consider every element 
        // as second element of GP 
        for (int j = n - 2; j >= 1; --j) 
        {
            // Search for i and k for j 
            int i = j - 1, k = j + 1;
            while (i >= 0 && k <= n - 1) 
            {
                // Two cases when i, j and k 
                // don't form a GP. 
                if (Set[i] * Set[k] < Set[j] * Set[j])
                {
                    ++k;
                
                else if (Set[i] * Set[k] > Set[j] * Set[j]) 
                {
                    if (Set[j] % Set[i] == 0) 
                    {
                        L[i,j] = 2;
                    
                    else
                    {
                        L[i,j] = 1;
                    }
                    --i;
                
                  
                // i, j and k form GP, LLGP with i and j as 
                // first two elements is equal to LLGP with 
                // j and k as first two elements plus 1. 
                // L[j,k] must have been filled before as 
                // we run the loop from right side 
                else
                {
                    L[i, j] = L[j, k] + 1;
  
                    // Update overall LLGP 
                    if (L[i, j] > llgp) 
                    {
                        llgp = L[i, j];
                    }
  
                    // Change i and k to fill more L[i,j] 
                    // values for current j 
                    --i;
                    ++k;
                }
            }
  
            // If the loop was stopped due to k becoming 
            // more than n-1, Set the remaining entties 
            // in column j as 1 or 2 based on divisibility 
            // of Set[j] by Set[i] 
            while (i >= 0) 
            {
                if (Set[j] % Set[i] == 0) 
                {
                    L[i, j] = 2;
                
                else
                {
                    L[i, j] = 1;
                }
                --i;
            }
        }
  
        // Return result 
        return llgp;
    }
  
    // Driver code 
    public static void Main(String[] args)
    {
        int []set1 = {1, 3, 9, 27, 81, 243};
        int n1 = set1.Length;
        Console.Write(lenOfLongestGP(set1, n1) + " ");
  
        int []set2 = {1, 3, 4, 9, 7, 27};
        int n2 = set2.Length;
        Console.Write(lenOfLongestGP(set2, n2) + " ");
  
        int []set3 = {2, 3, 5, 7, 11, 13};
        int n3 = set3.Length;
        Console.Write(lenOfLongestGP(set3, n3) + " ");
    }
}
  
// This code has been contributed by 29AjayKumar


Output:

6
4
1

Time Complexity: O(n2)
Auxiliary Space: O(n2)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter