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
wpDiscuz