Home » Interview » Array Interview Questions » Count of triplets with sum less than given value

Count of triplets with sum less than given value


In the given array, find the number of triplets with sum less than the given value.

Example

a)    Input array : [1,2,3,4,5,6,7,8]
Sum = 10

Output : 7
Possible triplets are : (1,2,3), (1,2,4), (1,2,5), (1,2,6), (1,3,4), (1,3,5), (2,3,4)

b)    Input array : [3, 7, 9, 1, 2, 5, 11, 4]
Sum = 10

Output : 6
Possible triplets are : (3,1,2), (3,1,5), (3,1,4), (3,2,4), (1,2,5), (1,2,4)

Method 1

Time Complexity : O(n3)

Algorithm

Step 1 : Run 3 nested loops, selecting all triplets possible.

Step 2 : Initialize result = 0.

Step 3 : If Sum of elements is less than Sum, increment count.

Step 4 : Print result as count of triplets satisfying the condition.

C++ Program

#include <bits/stdc++.h>
using namespace std;
 
//Main function
int main()
{
    int array[] = {3, 7, 9, 1, 2, 5, 11, 4};
    int N = sizeof(array)/sizeof(array[0]);
    int sum = 10;
    int result = 0;
    //First for loop for selecting first element
    //Second loop for second element
    //Third loop for third element.
    //check for triplets satisfing the condition, and increment result
    for (int i = 0; i < N-2; i++)
    {
       for (int j = i+1; j < N-1; j++)
       {
           for (int k = j+1; k < N; k++)
           {
               if(array[i]+array[j]+array[k] < sum)
                   {
                      result++;
                   }
           }
       }
    }
    cout<<"Number of Triplets found = ";
    cout<<result;
    return 0;
}

Method 2

Time Complexity : O(n2)

Algorithm

Step 1 : Sort the given array, initialize result = 0.

Step 2 : Iterate from i to N -2 (N is size of array), and take array[i] and first element of triplet.

Step 3 : Initialize other two elements as corner elements. array[i+1] and array[N-1].

READ  Sliding Window Maximum

Step 4 : move j and k until they meet do,

  1. If sum is greater than the given sum, then move pointer of last element. (array[N-1]).
  2. Else if sum is less than the given sum, then there can k -j possible tird elements satisfying, so add (k-j) to result. And move array[i+1] pointer.

Step 5 : Print result after ending the loop.

Algorithm working

C++ Program

#include <bits/stdc++.h>
using namespace std;
 
// Main function
int main()
{
    int array[] ={1, 2,3,5,6,};//input array
    int N = sizeof(array)/sizeof(array[0]);//size of the input array(N)
    int Sum = 10;//input Sum
    int result = 0;//initilizing count of triplets
    sort(array,array+N);//sorting the input array
    //selecting first element
    for(int i = 0; i < N - 2; i++)
    {
        int j=i+1,k=N-1;//second and third elements as last two elements
        while(j<k)
        {
            // Sum of triplet is greater than or equalto given sum, move to find smaller values
            if(array[i] + array[j] + array[k] >= Sum)
            {
                k--;
            }
            // Sum of triplet is less than given sum
            else
            {
                //for current i and j there can be k-j elements, move j pointer
                result += (k - j);
                j++;
            }
        }
    }
    cout<<"Number of Triplets found = ";
    cout<<result;
}

vote
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x