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