Print all triplets that form a geometric progression

Posted in

Print all triplets that form a geometric progression

Vinay Khatri
Last updated on June 8, 2022

    Problem

    Given a sorted array of distinct positive integers, print all triplets that form Geometric Progression. A geometric progression is a sequence of numbers where each term after the first is found by multiplying the previous one by a fixed, non-zero number called the common ratio. For example: 2, 6, 18 are GP triplets. Because 18/6 =  6/2

    Sample Input:

    [1, 2, 6, 10, 18, 54]

    Sample Output:

    2, 6, 8
    
    6, 18, 54

    Approach

    The idea is to start from the second element, each element should become a central element and the two other elements be searched in the array. For some element arr [j] is the centre of geometry progression triplet, elements arr [i] and arr [k] must be present, such that: arr[k] / arr[j] == arr[j] / arr[i].

    C++ Programming

    #include <iostream>
    using namespace std;
    
    void solve(int arr[], int n)
    {
    
       for (int j = 1; j < n - 1; j++)
       {
    
           int i = j - 1, k = j + 1;
    
          
           while (i >= 0 && k <= n - 1)
           {
              
               while (arr[j] % arr[i] == 0 &&
                       arr[k] % arr[j] == 0 &&
                       arr[j] / arr[i] == arr[k] / arr[j])
               {
              
                   cout << arr[i] << " " << arr[j]
                       << " " << arr[k] << endl;
                   k++ , i--;
               }
    
               if(arr[j] % arr[i] == 0 &&
                       arr[k] % arr[j] == 0)
               {
                   if(arr[j] / arr[i] < arr[k] / arr[j])
                       i--;
                   else k++;
               }
    
               else if (arr[j] % arr[i] == 0)
                   k++;
               else i--;
           }
       }
    }
    
    int main()
    {
       int arr[] = {1, 2, 4, 16};
       int n = sizeof(arr) / sizeof(arr[0]);
    
       solve(arr, n);
    }
    

    Output

    1 2 4
    1 4 16
    
    

    C Programming

    #include<stdio.h>
    void solve(int arr[], int n)
    {
    
       for (int j = 1; j < n - 1; j++)
       {
           int i = j - 1, k = j + 1;    
    
           while (i >= 0 && k <= n - 1)
           {       
               while (arr[j] % arr[i] == 0 &&
                       arr[k] % arr[j] == 0 &&
                       arr[j] / arr[i] == arr[k] / arr[j])
               {
                   printf("%d %d %d\n",arr[i],arr[j],arr[k]);
                   k++ , i--;
               }
    
               if(arr[j] % arr[i] == 0 &&
                       arr[k] % arr[j] == 0)
               {
                   if(arr[j] / arr[i] < arr[k] / arr[j])
                       i--;
                   else k++;
               }
    
               else if (arr[j] % arr[i] == 0)
                   k++;
               else i--;
           }
       }
    }
    
    int main()
    {
       int arr[] = {1, 2, 4, 16};
       int n = sizeof(arr) / sizeof(arr[0]);
       solve(arr, n);
    }

    Output

    1 2 4
    1 4 16

    Python Programming

    def solve(arr, n):
       for j in range(1, n - 1):
      
           i = j - 1
           k = j + 1
    
           while (i >= 0 and k <= n - 1):
          
               while (arr[j] % arr[i] == 0 and arr[k] % arr[j] == 0 and arr[j] // arr[i] == arr[k] // arr[j]):
                   print(str(arr[i])+" "+str(arr[j])+" "+str(arr[k]))
                   k += 1
                   i -= 1
    
               if(arr[j] % arr[i] == 0 and
                           arr[k] % arr[j] == 0):
              
                   if(arr[j]):
                       i -= 1
                   else:
                       k += 1
    
               elif (arr[j] % arr[i] == 0):
                   k += 1
               else:
                   i -= 1
    
      
    arr = [1, 2, 4, 16]
    n = len(arr)
    
    solve(arr, n)

    Output

    1 2 4
    1 4 16

    People are also reading:

    Leave a Comment on this Post

    0 Comments