Print all triplets that forms Geometric Progression

Given a sorted array of distinct positive integers, print all triplets that forms Geometric Progression with integral common ratio.

 
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, the sequence 2, 6, 18, 54,… is a geometric progression with common ratio 3.
 

For example,


Input: A[] = { 1, 2, 6, 10, 18, 54 }

Output:
2 6 18
6 18 54

Input: A[] = { 2, 8, 10, 15, 16, 30, 32, 64 }

Output:
2 8 32
8 16 32
16 32 64

Input: A[] = { 1, 2, 6, 18, 36, 54 }

Output:
2 6 18
1 6 36
6 18 54

Input: A[] = { 1, 2, 4, 16 }

Output:
1 2 4
1 4 16

Input: A[] = {1, 2, 3, 6, 18, 22};

Output:
2 6 18

 


 

We start from the second element and fix every element as middle element and search other two elements in a triplet (one smaller and one greater). We know that for an element A[j] to be middle of geometric progression, there exist elements A[i] and A[k] such that –

(A[j] / A[i] = r) and (A[k] / A[j] = r)

where r is an positive integer and (0 <= i < j) and (j < k <= n - 1).

C

Download   Run Code

Output:

2 6 18
6 18 54

Java

Download   Run Code

Output:

2 6 18
6 18 54

Time complexity of above solution is O(n2) as for every j, we are finding i and k in linear time and auxiliary space used by the program is O(1).

 
Author: Aditya Goel

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Rajib
Guest
Rajib

Simple way –

package com.practice;

public class GeometricProgression {

public static void main(String[] args) {
final int[] a = new int[] { 1, 2, 3, 6, 18, 22 };
geoProgression(a);

}

private static void geoProgression(int[] a) {
// loop to all elements
for (int i = 0; i < a.length – 3; i++) {
int element = a[i];
for (int j = i + 1; j < a.length; j++) {
int target = a[j];
if (target % element == 0) {
int r = target / element;
int possibleNext = r * target;
int k = j + 1;
// find out if possible next exists
while (k < a.length) {
int pp = a[k++];
if (pp == possibleNext) {
System.out.println(element + " " + target + " "
+ possibleNext);
break;
}
}
}
}
}
}

}

wpDiscuz