Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Brute Force approach
2.1.
Steps of Algorithm
2.2.
Implementation
2.2.1.
Code In Java:
2.2.2.
Code In C++:
2.2.3.
Complexity Analysis
3.
Optimized Approach
3.1.
Steps of Algorithm
3.2.
Implementation
3.2.1.
Code In Java:
3.2.2.
Code In C++:
3.2.3.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is the utilization of sizeof () function in C++?
4.2.
What does time complexity mean?
4.3.
What does space complexity mean?
4.4.
Which sorting is best for an array?
4.5.
How do you declare an Array in C++ and Java?
5.
Conclusion
Last Updated: Mar 27, 2024

Count triplets with sum smaller than a given value

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

This article will look at the problem of counting triplets with a sum smaller than a given value. Array-based questions are the most popular and vital in coding interviews and programming competitions. Let's understand the problem statement.

Problem Statement

We are given an array arr[] of different integers of size N and a value sum. The goal is to print the count of triplets (i, j, k) with the sum of triplets (arr[i] + arr[j] + arr[k]) smaller than the given value sum.

Sample Examples

Example 1:

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

Output 1:
4

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

 

Example 2:

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

Output 2: 
2

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

 

Also see, kth largest element in an array, and Euclid GCD Algorithm

Brute Force approach

In this method, we will run three loops to consider all triplets one by one. For every triplet, compare the sums and increment count if the triplet sum is smaller than the given sum. 

Steps of Algorithm

  1. Initialize the answer count as 0.
  2. Run the first loop from i=0 to less than (length-2) to get the first triplet.
  3. Run the second loop from j=i+1 to less than (length-1) to get the second triplet.
  4. To get the third triplet, run a loop from k=j+1 to less than (length).
  5. Add these triplets and check the condition if the sum is less than the required sum.
  6. Increment the count if condition satisfies.
  7. End the loop.

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

 

Code In C++:

#include<bits/stdc++.h>
#include<bits/stdc++.h>
using namespace std;
int countTriplets(int arr[], int n, int sum)
{
	int ans = 0;
	for (int i = 0; i < n-2; i++)
	{
	for (int j = i+1; j < n-1; j++)
	   {
		for (int k = j+1; k < n; k++)
			if (arr[i] + arr[j] + arr[k] < sum)
				ans++;
	}
	}
	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;
}

 

Output

4

 

Complexity Analysis

Time complexity: O(n^3) because of three nested loop

Space Complexity: O(1), we cannot use any extra memory

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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));
	}
}

 

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;
}

 

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 AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine 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 problemsinterview 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!!

Previous article
Find Element at Given Index After Several Rotations
Next article
The Suffix Matches
Live masterclass