Given a sorted array of distinct positive integers, print all triplets that forms Arithmetic Progression with integral common difference.

An Arithmetic Progression is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with common difference of 2.

**Input:** A[] = { 5, 8, 9, 11, 12, 15 }

**Output: **

5 8 11

9 12 15

**Input:** A[] = { 1, 3, 5, 6, 8, 9, 15 }

**Output: **

1 3 5

1 5 9

3 6 9

1 8 15

3 9 15

The idea is to consider every element as middle element of Arithmetic Progression starting from the second element and search other two elements of Arithmetic triplet. We know that for an element A[j] to be middle of Arithmetic progression, there exist two elements A[i] and A[k] such that –

(A[j] – A[i] = A[k] – A[j]) or (A[i] + A[k] == 2 * A[j])

where (0 <= i < j < k <= n - 1).

## C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include <stdio.h> // Function to print all triplets that forms Arithmetic Progression // in given sorted array void findAllTriplets(int A[], int n) { // consider A[j] as middle element of AP for (int j = 1; j < n - 1; j++) { // start with left and right index of j int i = j - 1, k = j + 1; // Find all i and k such that (i, j, k) forms a triplet of AP while (i >= 0 && k < n) { // if (A[i], A[j], A[k]) forms a triplet if (A[i] + A[k] == 2 * A[j]) { // print the triplet printf("%d %d %d\n", A[i], A[j], A[k]); // Since the array is sorted and elements are distinct k++, i--; } // else if (A[i] + A[k]) is less than 2*A[j] then // try next k. Else, try previous i. else if (A[i] + A[k] < 2 * A[j]) { k++; } else { i--; } } } } // main function int main(void) { int A[] = { 1, 3, 5, 6, 8, 9, 15 }; int n = sizeof(A) / sizeof(A[0]); findAllTriplets(A, n); return 0; } |

`Output:`

1 3 5

1 5 9

3 6 9

1 8 15

3 9 15

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
class ArithmeticProgression { // Function to print all triplets that forms Arithmetic Progression // in given sorted array public static void findAllTriplets(int[] A) { if (A.length < 3) { return; } // consider A[j] as middle element of AP for (int j = 1; j < A.length - 1; j++) { // start with left and right index of j int i = j - 1, k = j + 1; // Find all i and k such that (i, j, k) forms a triplet of AP while (i >= 0 && k < A.length) { // if (A[i], A[j], A[k]) forms a triplet if (A[i] + A[k] == 2 * A[j]) { // print the triplet System.out.println(A[i] + " " + A[j] + " " + A[k]); // Since the array is sorted and elements are distinct k++; i--; } // else if (A[i] + A[k]) is less than 2*A[j] then // try next k. Else, try previous i. else if (A[i] + A[k] < 2 * A[j]) { k++; } else { i--; } } } } public static void main(String[] args) { int[] A = { 1, 3, 5, 6, 8, 9, 15 }; findAllTriplets(A); } } |

`Output:`

1 3 5

1 5 9

3 6 9

1 8 15

3 9 15

Time complexity of above solution is O(n^{2}) as for every j, we are finding i and k in linear time and auxiliary space used by the program is O(1).

**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

We can do it by sorting and then traversing staring from 2nd element and checking its neighbour with the above formula and time complexity will be O(logN).

Thanks