## Sunday, August 7, 2016

### Find all triplets in a sorted array that forms Geometric Progression - GeeksforGeeks

Find all triplets in a sorted array that forms Geometric Progression - GeeksforGeeks
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.

The idea is to start from the second element and fix every element as middle element and search for the other two elements in a triplet (one smaller and one greater). For an element arr[j] to be middle of geometric progression, there must exist elements arr[i] and arr[k] such that –
```arr[j] / arr[i] = r and arr[k] / arr[j] = r
where r is an positive integer and 0 <= i < j and j < k <= n - 1```

Time complexity of above solution is O(n2) as for every j, we are finding i and k in linear time.
`void` `findGeometricTriplets(``int` `arr[], ``int` `n)`
`{`
`    ``// One by fix every element as middle element`
`    ``for` `(``int` `j = 1; j < n - 1; j++)`
`    ``{`
`        ``// Initialize i and k for the current j`
`        ``int` `i = j - 1, k = j + 1;`

`        ``// Find all i and k such that (i, j, k)`
`        ``// forms a triplet of GP`
`        ``while` `(i >= 0 && k <= n - 1)`
`        ``{`
`            ``// if arr[j]/arr[i] = r and arr[k]/arr[j] = r`
`            ``// and r is an integer (i, j, k) forms Geometric`
`            ``// Progression`
`            ``while` `(arr[j] % arr[i] == 0 &&`
`                    ``arr[k] % arr[j] == 0 &&`
`                    ``arr[j] / arr[i] == arr[k] / arr[j])`
`            ``{`
`                ``// print the triplet`
`                ``cout << arr[i] << ``" "` `<< arr[j]`
`                     ``<< ``" "` `<< arr[k] << endl;`

`                ``// Since the array is sorted and elements`
`                ``// are distinct.`
`                ``k++ , i--;`
`            ``}`

`            ``// if arr[j] is multiple of arr[i] and arr[k] is`
`            ``// multiple of arr[j], then arr[j] / arr[i] !=`
`            ``// arr[k] / arr[j]. We compare their values to`
`            ``// move to next k or previous 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] is multiple of arr[i], then`
`            ``// try next k. Else, try previous i.`
`            ``else` `if` `(arr[j] % arr[i] == 0)`
`                ``k++;`
`            ``else` `i--;`
`        ``}`
`    ``}`
`}`

Read full article from Find all triplets in a sorted array that forms Geometric Progression - GeeksforGeeks