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

 
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Rajib
Guest
Allen
Guest

Analogous to Arithmetic Progression problem, Suffices to consider the condition A[i]A[k] = A[j]^2 and increment k if the product is too small, decrement i if product too large.

https://ideone.com/e.js/rhNryk