# Count triplets with sum less than given value

Medium

Given an array with distinct elements, count triplets whose sum is less than a given value.

#### Example

Input: arr[] = {3, 5, 7, 9}

Sum = 6

Output: 1

Explanation: Below is the triplet with a sum less than 6 (3, 5, 7)

#### Example

Input: arr[] = {-1, 2, 4, 6, 8}

Sum = 10

Output: 5

Explanation: Below are triplets with a sum less than 10 (-1, 2, 4), (-1, 2, 6), (-1, 4, 6), (2, 4, 6), (-1, 2, 8)

#### Algorithm

- Sort the array in ascending order.
- Initialize a variable to keep track of the count of such triplets.
- Use two nested loops to select two elements from the array.
- Use a while loop to select the third element from the remaining elements.
- Check if the sum of the selected triplet is less than the given value. If it is, increment the count by the number of valid third elements.
- Continue the loops until all possible triplets are considered.
- Return the count of triplets that satisfy the condition.

#### Complexity

- Time Complexity: O(N^2), where N is the number of elements in the array.
- Space Complexity: O(1), because the code uses only a constant amount of extra space.

#### Code

```
## Java Code
import java.util.Arrays;
public class CountTripletsWithSumSmaller {
public static int countTripletsWithSumSmaller(int[] nums, int targetSum) {
Arrays.sort(nums); // Step 1: Sort the array
int n = nums.length;
int count = 0;
for (int i = 0; i < n - 2; i++) {
int left = i + 1;
int right = n - 1;
while (left < right) {
int currentSum = nums[i] + nums[left] + nums[right];
// Step 4: Check if the sum is smaller than the target
if (currentSum < targetSum) {
count += (right - left + 1); // Corrected counting logic
left++;
} else {
right--;
}
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {5, 1, 3, 4, 7};
int targetSum = 12;
int result = countTripletsWithSumSmaller(nums, targetSum);
System.out.println("Count of triplets with sum smaller than " + targetSum + " is " + result);
}
}
```

##### Output

```
Count of triplets with sum smaller than 12 is 4
```

Thanks for feedback.