13. Count triplets with sum smaller than x

13. Count triplets with sum smaller than x

Problem link :- click here

package program;

import java.util.Arrays;

public class Searching__13
{

	/*
	 	Given an array arr[] of distinct integers of size n and a sum value 'sum',
	 	the task is to find count of triplets with the sum smaller than the
	 	given sum value 'sum'
	 			arr[] = {-2, 0, 1, 3}		sum = 2
	 			output : 2
	 		
	 	we have to return the count of the triplets whose sum is less than 'sum'
	 	lets sort the array first and then
	 	we will take one element from for loop and other two elements from
	 	two pointer approach
	 */
	
	static int countOfTriplet(int arr[], int n, int sum)
	{
		//sorting the array
		Arrays.sort(arr);
		
		//finding the triplets whose sum is less than 'sum'
		int count = 0;
		for(int i=0; i<=n-3; i++)
		{
			int left, right;
			left = i+1;
			right = n-1;
			while(left < right)
			{
				int sum1 = arr[i] + arr[left] + arr[right];
				if(sum1 >= sum)
        				right--;
				else
				{
					count += right - left;
					left++;
				}
			}
		}
		
		return count;
	}
	
	
	public static void main(String[] args)
	{
		int arr[] = {5, 1, 3, 4, 7};
		int sum = 12;
		int ans = countOfTriplet(arr, arr.length, sum);
		System.out.print("Number of triplets whose sum is less than " + sum);
		System.out.println(" is : " + ans);
	}

}

Time complexity :- O(n^2)
Space complexity :- O(1)