Home » Technical Interview Questions » Array Interview Questions » Print all triplets in sorted array that form AP

Print all triplets in sorted array that form AP


The problem “Print all triplets in sorted array that form AP” states that we have given a sorted integer array. The task is to find out all the possible triplets that can form an Arithmetic Progression.

Print all triplets in sorted array that form AP

Example

arr[] = {1,3,5,7,8,12,15,16,20,30}
(1, 3, 5), (3, 5, 7), (1, 8, 15), (8, 12, 16), (12, 16, 20)

Explanation

These all are the triplets that form an A.P.

arr[] = {2,4,5,6,9,14,18,24}
(2, 4, 6), (4, 5, 6), (4, 9, 14), (4, 14, 24)

Explanation

These all are the triplets that form an A.P.

Algorithm

  1. Loop from i=1 to n-1(not included).
  2. Set the value of j to one less than i and value of k to one more than i.
  3. While j > = 0 && k < n.
    1. Check if the sum of the two current array elements is equal to twice of the other array element,
      1. If true, then print the current three elements and decrease and increase the value of k and j respectively.
    2. Check if the sum of the two elements is less than twice of another element, then, increase k by 1.
    3. Check if the sum of the two elements is greater than twice of another element, then, decrease j by 1.

Explanation

We have given a sorted array. We are asked to find out all the triplets that can form an Arithmetic Progression. An arithmetic progression can be defined as a number sequence in which all the elements come consecutively with a particular distance between them along the whole sequence. We will find the triplet by the formula of an AP which states a + c = 2b that is if the sum of the two numbers is equal to the twice of the third number.

READ  All Unique Triplets that Sum up to a Given Value

Traverse the whole array with one for loop and a while loop, ‘while loop’ is going to check if we find the three of the elements can form AP or not. We will set the value of j to one less than the value of i and value of k to one more than the value of i, whenever we traverse through the for loop. It will pick up an element for us to check, so every time we have three elements to check arr[i], arr[j], and arr[k], the value of i, j, and k that will vary for each traversal whether in for loop or in while loop.

If we found the sum of two elements is equal to the third element, we are going to print those three array elements, they can form an AP. We will update the value of j and k according to our algorithm. If we found the sum of two elements less than twice of the third element. We will increase the value of k, or if we found the sum greater than twice of the third element, we decrease the value of j. This will go on until we traverse the whole array and find out all the possible elements that can form an AP.

Code

C++ code to print all triplets in sorted array that form AP

#include<iostream>

using namespace std;

void getTripletsWithAP(int arr[], int n)
{
  for (int i = 1; i < n - 1; i++)
  {
    int j = i - 1, k = i + 1;
        while(j >= 0 && k < n)
        {
            if (arr[j] + arr[k] == 2 * arr[i])
            {
        cout <<arr[j]<< " "<<arr[i]<<" "<<arr[k]<< endl;
                k++;
                j--;
            }
            else if (arr[j] + arr[k] < 2 * arr[i])
                k++;
            else
                j--;
        }
  }
}
int main()
{
  int arr[] = {1,3,5,7,8,12,15,16,20,30};
  int n = sizeof(arr) / sizeof(arr[0]);
  getTripletsWithAP(arr, n);
  return 0;
}
1 3 5
3 5 7
1 8 15
8 12 16
12 16 20

Java code to Print all triplets in sorted array that form AP

class TripletAP
{
    public static void getTripletsWithAP(int arr[], int n)
    {
        for (int i = 1; i < n - 1; i++)
        {
            int j = i - 1, k = i + 1;
            while(j >= 0 && k < n)
            {
                if (arr[j] + arr[k] == 2 * arr[i])
                {
                    System.out.println(arr[j] +" " +arr[i]+ " " + arr[k]);
                    k++;
                    j--;
                }
                else if (arr[j] + arr[k] < 2 * arr[i])
                    k++;
                else
                    j--;
            }
        }
    }
    public static void main (String[] args)
    {
        int arr[] = {1,3,5,7,8,12,15,16,20,30};
        int n = arr.length;
        getTripletsWithAP(arr, n);
    }
}
1 3 5
3 5 7
1 8 15
8 12 16
12 16 20

Complexity Analysis

Time Complexity

O(n2where “n”  is the number of elements in the array. Because we have two nested loop where the first loop runs until we reach the end and then the second nested loop is used to find the elements of AP.

READ  Longest Increasing Subsequence

Space Complexity

O(1) as no extra space is required.

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup