Arithmetic Triplets - C++ Solution

1. Introduction

This blog post explores a problem involving arithmetic progressions in arrays. Given a sorted array of distinct positive integers, the challenge is to find all triplets that form an arithmetic progression with an integral common difference.

Problem

The objective is to identify all triplets within a sorted array of distinct positive integers that form an arithmetic progression, where the difference between consecutive terms is constant.

2. Solution Steps

1. Traverse the array using two nested loops.

2. For each pair of elements, calculate the common difference and check for the third element that completes the triplet.

3. Use binary search to find the third element efficiently as the array is sorted.

4. Store each valid triplet in a set to ensure uniqueness.

5. Return the set of all triplets forming arithmetic progressions.

3. Code Program

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

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

    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            int diff = nums[j] - nums[i];

            // Binary search for the third element
            if (binary_search(nums.begin() + j + 1, nums.end(), nums[j] + diff)) {
                triplets.insert({nums[i], nums[j], nums[j] + diff});
            }
        }
    }

    return triplets;
}

int main() {
    vector<int> nums = {5, 8, 9, 11, 12, 15};
    set<vector<int>> result = findArithmeticTriplets(nums);

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

    return 0;
}

Output:

{5 8 11}
{9 12 15}

Explanation:

The function findArithmeticTriplets identifies all triplets that form an arithmetic progression. It iterates through each pair of elements in the sorted array and uses binary search to find a third element that forms an arithmetic progression with the pair. For the input array [5, 8, 9, 11, 12, 15], it successfully finds the triplets [5, 8, 11] and [9, 12, 15] that form arithmetic progressions.