Print all triplets that form a geometric progression

By | November 17, 2021

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]

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