Print all triplets that form a geometric progression

By | November 17, 2021
Print all triplets that form a geometric progression

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].

Vamware

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

Vamware
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:

Author: Vinay

I am a Full Stack Developer with a Bachelor's Degree in Computer Science, who also loves to write technical articles that can help fellow developers.

Leave a Reply

Your email address will not be published.