Given an array of distinct integers and a sum value. Print all triplets with sum smaller than given sum value. Expected Time Complexity is O(n2).
Examples:
Input : arr[] = {-2, 0, 1, 3}
sum = 2.
Output : (-2, 0, 1)
(-2, 0, 3)
Explanation : The two triplets have sum less than 2.
Input : arr[] = {5, 1, 3, 4, 7}
sum = 12.
Output : (1, 3, 4)
(1, 3, 5)
(1, 3, 7)
(1, 4, 5)
A Simple Solution is to run three loops to consider all triplets one by one. For every triplet, compare the sums and print current triplet if its sum is smaller than given sum.
Implementation:
C++
// A Simple C++ program to count triplets with sum// smaller than a given value#include<bits/stdc++.h>using namespace std;int printTriplets(int arr[], int n, int sum){ // Fix the first element as A[i] for (int i = 0; i < n-2; i++) { // Fix the second element as A[j] for (int j = i+1; j < n-1; j++) { // Now look for the third number for (int k = j+1; k < n; k++) if (arr[i] + arr[j] + arr[k] < sum) cout << arr[i] << ", " << arr[j] << ", " << arr[k] << endl; } }}// Driver programint main(){ int arr[] = {5, 1, 3, 4, 7}; int n = sizeof arr / sizeof arr[0]; int sum = 12; printTriplets(arr, n, sum); return 0;} |
Java
// A Simple Java program to // count triplets with sum // smaller than a given valueimport java.io.*;class GFG {static int printTriplets(int arr[], int n, int sum){ // Fix the first // element as A[i] for (int i = 0; i < n - 2; i++) { // Fix the second // element as A[j] for (int j = i + 1; j < n - 1; j++) { // Now look for // the third number for (int k = j + 1; k < n; k++) if (arr[i] + arr[j] + arr[k] < sum) System.out.println(arr[i] + ", " + arr[j] + ", " + arr[k]); } } return 0;}// Driver Codepublic static void main (String[] args){ int arr[] = {5, 1, 3, 4, 7}; int n = arr.length; int sum = 12; printTriplets(arr, n, sum);}}// This code is contributed// by anuj_67. |
Python3
# A Simple python 3 program to count # triplets with sum smaller than a # given valuedef printTriplets(arr, n, sum): # Fix the first element as A[i] for i in range(0, n - 2, 1): # Fix the second element as A[j] for j in range(i + 1, n - 1, 1): # Now look for the third number for k in range(j + 1, n, 1): if (arr[i] + arr[j] + arr[k] < sum): print(arr[i], ",", arr[j], ",", arr[k])# Driver Codeif __name__ == '__main__': arr =[5, 1, 3, 4, 7] n = len(arr) sum = 12 printTriplets(arr, n, sum) # This code is contributed by# Sahil_Shelangia |
C#
// A Simple C# program to // count triplets with sum // smaller than a given valueusing System;class GFG {static int printTriplets(int[] arr, int n, int sum){ // Fix the first // element as A[i] for (int i = 0; i < n - 2; i++) { // Fix the second // element as A[j] for (int j = i + 1; j < n - 1; j++) { // Now look for // the third number for (int k = j + 1; k < n; k++) if (arr[i] + arr[j] + arr[k] < sum) Console.WriteLine(arr[i] + ", " + arr[j] + ", " + arr[k]); } } return 0;}// Driver Codepublic static void Main (){ int[] arr = {5, 1, 3, 4, 7}; int n = arr.Length; int sum = 12; printTriplets(arr, n, sum);}}// This code is contributed// by Mukul Singh. |
PHP
<?php// A Simple PHP program to count triplets // with sum smaller than a given valuefunction printTriplets(&$arr, $n, $sum){ // Fix the first element as A[i] for ($i = 0; $i < $n - 2; $i++) { // Fix the second element as A[j] for ($j = $i + 1; $j < $n - 1; $j++) { // Now look for the third number for ($k = $j + 1; $k < $n; $k++) if ($arr[$i] + $arr[$j] + $arr[$k] < $sum) { echo($arr[$i]); echo(", " ); echo($arr[$j]); echo(", "); echo($arr[$k]); echo("\n"); } } }}// Driver Code$arr = array(5, 1, 3, 4, 7);$n = sizeof($arr);$sum = 12;printTriplets($arr, $n, $sum);// This code is contributed // by Shivi_Aggarwal ?> |
Javascript
<script>// A Simple JavaScript program to // count triplets with sum// smaller than a given valuefunction printTriplets(arr, n, sum){ // Fix the first element as A[i] for (let i = 0; i < n-2; i++) { // Fix the second element as A[j] for (let j = i+1; j < n-1; j++) { // Now look for the third number for (let k = j+1; k < n; k++) if (arr[i] + arr[j] + arr[k] < sum) document.write(arr[i] + ", " + arr[j] + ", " + arr[k] + "<br>"); } }}// Driver program let arr = [5, 1, 3, 4, 7]; let n = arr.length; let sum = 12; printTriplets(arr, n, sum);// This code is contributed by Surbhi Tyagi.</script> |
Output
5, 1, 3 5, 1, 4 1, 3, 4 1, 3, 7
Time complexity : O(n3)
Auxiliary Space: O(1)
An Efficient Solution can print triplets in O(n2) by sorting the array first, and then using method 1 of this post in a loop.
1) Sort the input array in increasing order.
2) Initialize result as 0.
3) Run a loop from i = 0 to n-2. An iteration of this loop
finds all triplets with arr[i] as first element.
a) Initialize other two elements as corner elements
of subarray
arr[i+1..n-1], i.e., j = i+1 and k = n-1
b) Move j and k toward each other until they meet,
i.e., while (j = sum), then do k--
// Else for current i and j, there are (k-j) possible
// third elements that satisfy the constraint.
(ii) Else print elements from j to k
Below is the implementation of above idea.
C++
// C++ program to print triplets with sum smaller// than a given value#include <bits/stdc++.h>using namespace std;int printTriplets(int arr[], int n, int sum){ // Sort input array sort(arr, arr + n); // Every iteration of loop counts triplet with // first element as arr[i]. for (int i = 0; i < n - 2; i++) { // Initialize other two elements as corner // elements of subarray arr[j+1..k] int j = i + 1, k = n - 1; // Use Meet in the Middle concept while (j < k) { // If sum of current triplet is more or equal, // move right corner to look for smaller values if (arr[i] + arr[j] + arr[k] >= sum) k--; // Else move left corner else { // This is important. For current i and j, // there are total k-j third elements. for (int x = j + 1; x <= k; x++) cout << arr[i] << ", " << arr[j] << ", " << arr[x] << endl; j++; } } }}// Driver programint main(){ int arr[] = { 5, 1, 3, 4, 7 }; int n = sizeof arr / sizeof arr[0]; int sum = 12; printTriplets(arr, n, sum); return 0;} |
Java
// Java program to print// triplets with sum smaller// than a given valueimport java.util.*;import java.lang.*;import java.io.*;class GFG{static void printTriplets(int arr[], int n, int sum){ // Sort input array Arrays.sort(arr); // Every iteration of loop // counts triplet with // first element as arr[i]. for (int i = 0; i < n - 2; i++) { // Initialize other two elements // as corner elements of subarray // arr[j+1..k] int j = i + 1, k = n - 1; // Use Meet in the // Middle concept while (j < k) { // If sum of current triplet // is more or equal, move right // corner to look for smaller values if (arr[i] + arr[j] + arr[k] >= sum) k--; // Else move left corner else { // This is important. For // current i and j, there // are total k-j third elements. for (int x = j + 1; x <= k; x++) System.out.println(arr[i] + ", " + arr[j] + ", " + arr[x]); j++; } } }}// Driver Codepublic static void main(String args[]){ int arr[] = { 5, 1, 3, 4, 7 }; int n = arr.length; int sum = 12; printTriplets(arr, n, sum);}}// This code is contributed// by Subhadeep |
Python3
# Python3 program to print# triplets with sum smaller# than a given valuedef printTriplets(arr, n, sum): # Sort input array arr.sort() # Every iteration of loop # counts triplet with # first element as arr[i]. for i in range(n - 2): # Initialize other two elements # as corner elements of subarray # arr[j+1..k] (j, k) = (i + 1, n - 1) # Use Meet in the # Middle concept while (j < k): # If sum of current triplet # is more or equal, move right # corner to look for smaller values if (arr[i] + arr[j] + arr[k] >= sum): k -= 1 # Else move left corner else: # This is important. For # current i and j, there # are total k-j third elements. for x in range(j + 1, k + 1): print(str(arr[i]) + ", " + str(arr[j]) + ", " + str(arr[x])) j += 1# Driver codeif __name__=="__main__": arr = [ 5, 1, 3, 4, 7 ] n = len(arr) sum = 12 printTriplets(arr, n, sum);# This code is contributed by rutvik_56 |
C#
// C# program to print// triplets with sum smaller// than a given valueusing System;class GFG{static void printTriplets(int[] arr, int n, int sum){ // Sort input array Array.Sort(arr); // Every iteration of loop // counts triplet with // first element as arr[i]. for (int i = 0; i < n - 2; i++) { // Initialize other two elements // as corner elements of subarray // arr[j+1..k] int j = i + 1, k = n - 1; // Use Meet in the // Middle concept while (j < k) { // If sum of current triplet // is more or equal, move right // corner to look for smaller values if (arr[i] + arr[j] + arr[k] >= sum) k--; // Else move left corner else { // This is important. For // current i and j, there // are total k-j third elements. for (int x = j + 1; x <= k; x++) Console.WriteLine(arr[i] + ", " + arr[j] + ", " + arr[x]); j++; } } }}// Driver Codepublic static void Main(){ int[] arr = { 5, 1, 3, 4, 7 }; int n = arr.Length; int sum = 12; printTriplets(arr, n, sum);}}// This code is contributed// by Akanksha Rai |
PHP
<?php// PHP program to print triplets with // sum smaller than a given valuefunction printTriplets($arr, $n, $sum){ // Sort input array sort($arr, 0); // Every iteration of loop counts // triplet with first element as arr[i]. for ($i = 0; $i < $n - 2; $i++) { // Initialize other two elements as corner // elements of subarray arr[j+1..k] $j = $i + 1; $k = $n - 1; // Use Meet in the Middle concept while ($j < $k) { // If sum of current triplet is more // or equal, move right corner to // look for smaller values if ($arr[$i] + $arr[$j] + $arr[$k] >= $sum) $k--; // Else move left corner else { // This is important. For current i and j, // there are total k-j third elements. for ($x = $j + 1; $x <= $k; $x++) echo $arr[$i] . ", " . $arr[$j] . ", " . $arr[$x] . "\n"; $j++; } } }}// Driver Code$arr = array(5, 1, 3, 4, 7);$n = sizeof($arr);$sum = 12;printTriplets($arr, $n, $sum);// This code is contributed // by Akanksha Rai?> |
Javascript
<script> // JavaScript program to print // triplets with sum smaller // than a given value function printTriplets(arr, n, sum) { // Sort input array arr.sort(function(a, b){return a - b}); // Every iteration of loop // counts triplet with // first element as arr[i]. for (let i = 0; i < n - 2; i++) { // Initialize other two elements // as corner elements of subarray // arr[j+1..k] let j = i + 1, k = n - 1; // Use Meet in the // Middle concept while (j < k) { // If sum of current triplet // is more or equal, move right // corner to look for smaller values if (arr[i] + arr[j] + arr[k] >= sum) k--; // Else move left corner else { // This is important. For // current i and j, there // are total k-j third elements. for (let x = j + 1; x <= k; x++) document.write(arr[i] + ", " + arr[j] + ", " + arr[x] + "</br>"); j++; } } } } let arr = [ 5, 1, 3, 4, 7 ]; let n = arr.length; let sum = 12; printTriplets(arr, n, sum); </script> |
Output
1, 3, 4 1, 3, 5 1, 3, 7 1, 4, 5
Time Complexity: O(N*N)
Auxiliary Space: O(1)
Print triplets with sum less than k in python:
Python3
# program to print all triplets with sum less than kdef print_triplets(arr, k): n = len(arr) count = 0 # sort the array in non-decreasing order arr.sort() # iterate through all possible triplets for i in range(n-2): j = i+1 k = n-1 while j < k: # calculate the sum of the triplet triplet_sum = arr[i] + arr[j] + arr[k] # if the sum is less than k, print the triplet and update the count if triplet_sum < k: print(arr[i], arr[j], arr[k]) count += 1 j += 1 # if the sum is greater than or equal to k, decrement k else: k -= 1 # return the count of triplets with sum less than k return count# example usagearr = [5, 1, 3, 4, 7]k = 12count = print_triplets(arr, k)print("Total number of triplets with sum less than", k, "is", count) |
Output
Total number of triplets with sum less than 12 is 0
Time Complexity: O(N^2)
Auxiliary Space: O(1)
Approach:
1.Define a function print_triplets that takes two arguments: an array arr and an integer k. The function will return the count of triplets with sum less than k.
2.Get the length of the array n, and initialize a variable count to 0 to keep track of the number of triplets.
3.Sort the input array arr in non-decreasing order, using the built-in sort() function. This is done to simplify the algorithm and allow us to stop iterating when we find a triplet with sum greater than or equal to k.
4.Use a nested loop to iterate through all possible triplets of the input array arr. The outer loop will iterate from the first element to the second to last element, while the inner loop will iterate from the element following the current outer loop element to the last element.
5.For each triplet, calculate the sum of the triplet triplet_sum as the sum of the current outer loop element, the current inner loop element, and the last element of the array.
6.If triplet_sum is less than k, print the triplet and increment the count variable by 1.
7.If triplet_sum is greater than or equal to k, decrement the index of the last element of the array to move to the next smaller element, and continue checking triplets.
8.After iterating through all possible triplets, return the count of triplets with sum less than k.
9.In the example usage, create an input array arr and an integer k, and call the print_triplets function with these arguments. Finally, print the total number of triplets found.
Time complexity: O(n^2), where n is the size of the input array
Space complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
