Geometric Progression Triplets - C++ Solution

1. Introduction

In this post, we delve into a problem related to finding geometric progressions in arrays. The task is to identify all triplets in a sorted array of distinct positive integers that form a geometric progression with an integral common ratio.

Problem

Given a sorted array of distinct positive integers, we need to find all triplets that form a geometric progression with an integral common ratio. A geometric progression is a sequence of numbers where each term is found by multiplying the previous term by a fixed, non-zero number known as the common ratio.

2. Solution Steps

1. Iterate through the array to consider each element as a potential middle term of the geometric progression triplet.

2. For each middle term, find potential first and third terms by considering the ratios with other elements.

3. Use a set to store triplets to ensure uniqueness.

4. Return the set of all triplets forming geometric progressions.

3. Code Program

#include <iostream>
#include <vector>
#include <set>
using namespace std;

set<vector<int>> findGeometricTriplets(const vector<int>& nums) {
    set<vector<int>> triplets;
    int n = nums.size();

    for (int i = 1; i < n - 1; i++) {
        int a = nums[i];
        for (int j = 0; j < i; j++) {
            for (int k = i + 1; k < n; k++) {
                int b = nums[j], c = nums[k];
                if (a % b == 0 && c % a == 0 && a / b == c / a) {
                    triplets.insert({b, a, c});
                }
            }
        }
    }

    return triplets;
}

int main() {
    vector<int> nums = {1, 2, 6, 10, 18, 54};
    set<vector<int>> result = findGeometricTriplets(nums);

    // Output the result
    for (const auto& triplet : result) {
        cout << "{";
        for (int num : triplet) {
            cout << num << " ";
        }
        cout << "}\n";
    }

    return 0;
}

Output:

{2 6 18}
{6 18 54}

Explanation:

The function findGeometricTriplets identifies all triplets that form a geometric progression in the given sorted array. It iterates over each element, considering it as the middle term of a potential triplet, and then searches for corresponding first and third terms that satisfy the geometric progression conditions. For example, in the input array [1, 2, 6, 10, 18, 54], it successfully finds the triplets [2, 6, 18] and [6, 18, 54] that form geometric progressions.