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.