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