Count triplets with sum smaller than a given value

Optimized Approach

We count triplets in O(n^2) by sorting the array first. Then we fix a value and look for a pair having sum equal to the given number in a loop. Given below is a diagrammatic representation of this approach:

After this the loop ends and we return the answer.

Steps of Algorithm

1. Sort the array
2. Initialize result=0
3. Run a loop from i=0 to i<n-2. This loop finds all triplets with first number fixed as arr[i].
4. Inside this loop, we initialize corner elements of array i.e. arr[i+1..n-1]

 as j=i+1 and k=n-1. Then we check the following conditions:

1. while (j<k)

If arr[i] + arr[j] + arr[k] >= sum, then  we decrement k

Else for current i and j there can be (k-j) possible solutions, so we do ans += (k - j) and increment j.

Implementation

Code In Java:

import java.util.Arrays;
class Test
{
	static int arr[] = new int[]{3, 4, 7, 5, 1};
	static int countTriplets(int n, int sum)
	{
Arrays.sort(arr);//sort the array
		int ans = 0;

		for (int i = 0; i < n - 2; i++)
		{
			int j = i + 1, k = n - 1;
			while (j < k)
			{
				if (arr[i] + arr[j] + arr[k] >= sum)
					k--;
				else
				{
					ans += (k - j);
					j++;
				}
			}
		}
		return ans;
	}
	
	// driver method 
	public static void main(String[] args)
	{
		int sum = 12;
		System.out.println(countTriplets(arr.length, sum));
	}
}

You can also try this code with Online Java Compiler

Run Code

Code In C++:

#include<bits/stdc++.h>
using namespace std;
int countTriplets(int arr[], int n, int sum)
{
	sort(arr, arr+n);
	int ans = 0;

	for (int i = 0; i < n - 2; i++)
	{
		int j = i + 1, k = n - 1;
		while (j < k)
		{
			if (arr[i] + arr[j] + arr[k] >= sum)
				k--;
			else
			{
				ans += (k - j);
				j++;
			}
		}
	}
	return ans;
}

// Driver program
int main()
{
	int arr[] = {3, 4, 7, 5, 1};
	int n = sizeof arr / sizeof arr[0];
	int sum = 12;
	cout << countTriplets(arr, n, sum) << endl;
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output: 

4

Complexity Analysis

Time complexity: O(n^2) we use sort and 2 nested loop O(nlogn + n^2) = O(n^2)

Space Complexity: O(1)

Frequently Asked Questions

What is the utilization of sizeof () function in C++?

The sizeof keyword is a compile-time operator for determining the size of a variable or data type in bytes.

Syntax:

sizeof (data type)

What does time complexity mean?

The time complexity in computer science is the computational complexity that describes how long it takes a computer to run an algorithm. Choosing the most efficient algorithm is always better when a fundamental problem can be solved using multiple methods.

What does space complexity mean?

The space complexity of an algorithm is the total space taken by the algorithm with respect to the input size. In simple words, An algorithm's amount of memory is known as its space complexity.

Which sorting is best for an array?

The quicksort algorithm is better if the size of the input is vast. But, insertion sort is more efficient than quicksort if the array is of small size as the number of swaps and comparisons are less than quicksort. So we combine the two algorithms to sort efficiently using both approaches.

How do you declare an Array in C++ and Java?

An array is fixed in length i.e. static in nature.

Array declaration syntax in C/C++: DataType ArrayName [size];

Array declaration in Java: It is done by giving a type and name: int[] ArrayName; To initialize an array as we declare it, meaning we assign values when we create the array, we can utilize the following shorthand syntax: int[] ArrayName = {5, 8, 9};

Conclusion

This article discussed the solution for segregating 0s and 1s in an array along with its different approaches, pseudocode, implementation, and code in both JAVA and C++.

Check out this problem - Pair Sum In Array.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, Machine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!