## 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].

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

- If sum is greater than the given sum, then move pointer of last element. (array[N-1]).
- 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;
}
```