Print all Triplets that forms Arithmetic Progression

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.
 

For example,


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

Download   Run Code

Output:

1 3 5
1 5 9
3 6 9
1 8 15
3 9 15

Java

Download   Run Code

Output:

1 3 5
1 5 9
3 6 9
1 8 15
3 9 15

Time complexity of above solution is O(n2) 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 ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz