# Count Triplets with Sum Smaller Than X in Java

Given an array arr [] of distinct integers and a sum value. The task is to find the count of triplets with a sum smaller than the given sum value.

Example 1

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

`sum = 12`

Output: 4

Explanation: Below are triplets with sum less than 12 are (1, 3, 4), (1, 3, 5), (1, 3, 7) and (1, 4, 5).

Example 2

Input: arr [] = {0, -2, 1, 3}

`Sum = 2`

Output: 2

Explanation: The triplets with sum less than 2 are (0, -2, 1) and (0, -2, 3).

Example 3

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

`Sum = 12`

Output: 4

Explanation: The triplets with sum less than 12 are (1, 3, 4), (1, 3, 5), (1, 3, 7) and (1, 4, 5).

## Approach 1: Using Brute Force

A Brute Force approach is to consider all the triplets by iterating through the array using 3 loops, each loop for each element of triplet. Only those triplets will be consider whose overall sum is less than the desired sum value.

### Algorithm

Step 1: Initialize an initial count of triplets set to 0.

Step 2: Iterate through each possible combination of triplets in the array using three nested loops.

Step 3: For each triplet, calculate the sum of its elements.

Step 4: Compare the sum with the given value sum.

Step 5: If the sum of the current triplet is smaller than given sum value, increment the count of triplets.

Step 6: Return the count of triplets satisfying the condition.

Filename: TripletsWithSumSmallerThanXUsingBruteForce.java

`public class TripletsWithSumSmallerThanXUsingBruteForce {    // Function to count triplets with sum smaller than X using brute force approach    public static int countTripletsBruteForce(int[] arr, int X) {        int count = 0; // Initialize count of triplets        // Iterate through each possible triplet combination        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++) {                    // Check if sum of current triplet is smaller than X                    if (arr[i] + arr[j] + arr[k] < X) {                        count++; // Increment count if sum is smaller than X                    }                }            }        }        return count; // Return the count of triplets    }    // Main method to test the function    public static void main(String[] args) {       // Input array        int [] arr = {5, 1, 3, 4, 7};       // Given value X        int X = 12;        // Call the function and print the result        System.out.println("Count of triplets with sum smaller than " + X + ": " + countTripletsBruteForce(arr, X));    }}`

Output

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

Time Complexity: The time complexity of the brute force approach is O(n^3), where n is the size of the array. This is because the algorithm involves three nested loops, each iterating over the array of size n.

Space Complexity: The space complexity of the brute force approach is constant O(1). This is because it doesn't require any additional space that grows with the input size.

## Approach 2: Using Sorting Technique

A Sorting Technique involves sorting the array first and then applying the meet in the middle approach to effectively count all the possible cases of triplets without going through all the triplets. We create two pointers, which take into account the left index and right index of the sorted array.

### Algorithm

Step 1: First sort the given array in non-decreasing order. Sorting allows us to efficiently find triplets that satisfy the condition by leveraging the properties of the sorted array.

Step 2: Next, we iterate through each element of the array, considering it as the first element of the triplet.

Step 3: For each selected first element, we use a two-pointer technique to find the other two elements that, when combined with the first element, form a triplet with a sum less than given sum value.

Step 4: Count the number of triplets that satisfy the condition of having a sum smaller than given sum value.

Step 5: Return the count as result.

Filename: TripletsWithSumSmallerThanXUsingSorting.java

`import java.util.Arrays;public class TripletsWithSumSmallerThanXUsingSorting {    // Function to count triplets with sum smaller than X using sorting approach    public static int countTripletsSorting(int[] arr, int X) {       // Sort the array in non-decreasing order        Arrays.sort(arr);        // Initialize count of triplets        int count = 0;        // Length of the sorted array        int n = arr.length;        // Iterate through each element as the first element of the triplet        for (int i = 0; i < n - 2; i++) {            int left = i + 1; // Pointer for the second element            int right = n - 1; // Pointer for the third element            // Using two-pointer technique to find the other two elements            while (left < right) {                // Calculate the sum of current triplet                int sum = arr[i] + arr[left] + arr[right];                // If sum is smaller than X, increment count and move the left pointer to the right                if (sum < X) {                    count += right - left;                    left++;                }                // If sum is greater than or equal to X, move the right pointer to the left                else {                    right--;                }            }        }        return count; // Return the count of triplets    }    // Main method to test the function    public static void main(String[] args) {        int[] arr = {5, 1, 3, 4, 7}; // Input array        int X = 12; // Given value X        // Call the function and print the result        System.out.println("Count of triplets with sum smaller than " + X + ": " + countTripletsSorting(arr, X));    }}`

Output

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

Time Complexity: The time complexity of an algorithm is ((n log n), where n is the size of an array. This is because for each element in an array, we use a two-pointer technique.

Space Complexity: The space complexity of the sorting approach is O(1). This is because it only requires a constant amount of extra space for variables and pointers.

## Approach 3: Using Binary Search

A Binary Search approach is to count the number of triplets in an array whose sum is smaller than a given sum value.

### Algorithm

Step 1: Sort the given array in non-decreasing order to simplify the process.

Step 2: Iterate through all possible pairs of the array (using two nested loops).

Step 3: For each pair, calculate the remaining sum needed to reach the given sum value.

Step 4: Use binary search to find the index of the last element less than the remaining sum.

Step 5: Add the count of triplets with this index to the total count.

Filename: CountTripletsWithSumSmallerThanXUsingBinarySearch.java

`import java.util.Arrays;public class CountTripletsWithSumSmallerThanXUsingBinarySearch {    public static void main(String[] args) {        // Sample array and target sum        int[] arr = {5, 1, 3, 4, 7};        int target = 12;        // Print the count of triplets with sum smaller than the target        System.out.println("Count of triplets with sum smaller than " + target + ": " + countTriplets(arr, target));    }    // Function to count triplets with sum smaller than a given target    public static int countTriplets(int[] arr, int target) {        // Sorting the array        Arrays.sort(arr);        int n = arr.length;        int count = 0;        // Iterating through all possible triplets        for (int i = 0; i < n - 2; i++) {            for (int j = i + 1; j < n - 1; j++) {                // Calculating the remaining sum needed for the triplet                int remaining = target - arr[i] - arr[j];                // Finding the index of the last element less than remaining                int index = binarySearch(arr, j + 1, n - 1, remaining);                // If such element exists, count all triplets with this index                if (index > j) {                    count += index - j;                }            }        }        return count;    }    // Binary search function to find the index of the last element less than target    private static int binarySearch(int[] arr, int left, int right, int target) {        while (left <= right) {            int mid = left + (right - left) / 2;            if (arr[mid] < target) {                left = mid + 1;            } else {                right = mid - 1;            }        }        return right;    }}`

Output

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

Time Complexity: The time complexity of a Binary Search algorithm is O(n^2 log n), where n is the size of the array. This is because each iteration of the nested loops takes O(n^2) and Binary search takes (log n) for each iteration.

Space Complexity: The space complexity of an algorithm is O(1). This is because it doesn't require any additional space that grows with the input size.