Count of Triplets With Sum Less than Given Value


Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg ByteDance Cisco Citadel Citrix DoorDash eBay Facebook Goldman Sachs Google Hulu IBM Infosys Mathworks Microsoft Oracle PayPal Qualtrics Samsung ServiceNow Splunk Square Tencent Tesla Uber Visa VMware Walmart Labs Yahoo Zoho
Akamai Array Groupon Postmates Two Pointer Two Pointers Works Applications

Problem Statement

We have given an array containing N number of elements. In the given array, Count the number of triplets with a sum less than the given value.

Example

Input

a[] = {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)

Input

a[]  = {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)

Approach 1

Algorithm

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

2. Initialize result = 0.

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

4. Print results as a count of triplets satisfying the condition.

Implementation

C++ Program for Count of Triplets With Sum Less than Given Value

#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;
}
Number of Triplets found = 6

Java Program for Count of Triplets With Sum Less than Given Value

import static java.lang.Math.pow;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int sum = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        //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
        int result=0;
        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(a[i]+a[j]+a[k] < sum)
                       {
                          result++;
                       }
               }
           }
        }
        System.out.print("Number of Triplets found = ");
        System.out.println(result);
    }
}
5 6
1 2 3 2 1
Number of Triplets found = 5

Complexity Analysis

Time Complexity

O(n*n*n) where n is the size of the given array. Here we check for all the triplets and if the condition is true then increase the count of the result.

Space Complexity

O(1) because we don’t use any auxiliary space here.

Approach 2

Algorithm

1. Sort the given array, initialize result = 0

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

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

4. move j and k until they meet to do,

  1. If the sum is greater than the given sum, then move the pointer of the last element. (array[N-1]).
  2. Else if the 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 the result after ending the loop.

Implementation

C++ Program for Count of Triplets With Sum Less than Given Value

#include <bits/stdc++.h>
using namespace std;
 
// Main function
int main()
{
    int array[] ={1, 2,3,5,6, 3, 2, 5, 7};//input array
    int N = sizeof(array)/sizeof(array[0]);//size of the input array(N)
    int Sum = 9;//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;
}
Number of Triplets found = 14

Java Program for Count of Triplets With Sum Less than Given Value

import static java.lang.Math.pow;
import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int sum = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        //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
        int result=0;
        Arrays. sort(a);//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(a[i] + a[j] + a[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++;
                }
            }
        }
        System.out.print("Number of Triplets found = ");
        System.out.println(result);
    }
}
9 9
1 2 3 5 6 3 2 5 7
Number of Triplets found = 14

Complexity Analysis

Time Complexity

O(n*n) where n is the number of elements present in the array. Here we fix one element of the triplet and then using two pointer methods that run O(N) in the worst case for one element.

Space Complexity

O(1) because we don’t use any auxiliary space here.

References

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