**13**

*Jul*

*2018*

### Triplet counts with sum smaller than given Number

We are given an array of distinct integers and along with it a sum value. We have to find count of triplets with sum that is smaller than the sum value. First we will solve in N^3 Time complexity. then we will be optimizing our current solution for better time complexity.

```
Example:
Input : arr[] = {6, 2, 4, 5, 8}
sum = 17.
Output : 4
Explanation : triplets with sum less than 17 are
(2, 4, 5), (2, 4, 6), (2, 4, 8) and
(2, 5, 6)
```

```
public class CountTriplets {
private static int calculateTriplets(int[] arr, int sum) {
//n^3 solution.
int count=0;
for(int i=0;i<arr.length-2;i++) {
for(int j=i+1;j<arr.length-1;j++) {
for(int k=j+1;k<arr.length;k++) {
if((arr[i]+arr[j]+arr[k]) < sum)
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[] arr= new int[] {6, 2, 4, 5, 8};
int sum = 15;
System.out.println(calculateTriplets(arr,sum));
}
}
```

Now we will optimize the solution for time complexity N^2.

```
import java.util.Arrays;
public class CountTriplets {
private static int calculateTriplets(int[] arr, int sum) {
//n^2 solution.
int count=0;
Arrays.sort(arr);
for(int i=0;i<arr.length-2;i++) {
int j=i+1;
int k=arr.length-1;
while(j<k) {
if((arr[i]+arr[j]+arr[k])<sum) {
count+=k-j;
j++;
}
else
k--;
}
}
return count;
}
public static void main(String[] args) {
int[] arr= new int[] {6, 2, 4, 5, 8};
int sum = 15;
System.out.println(calculateTriplets(arr,sum));
}
}
```