Dada una array de enteros distintos y un valor de suma. Imprima todos los tripletes con una suma menor que el valor de suma dado. La Complejidad de Tiempo Esperada es O(n 2 ).
Ejemplos :
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)
Una solución simple es ejecutar tres bucles para considerar todos los tripletes uno por uno. Para cada triplete, compare las sumas e imprima el triplete actual si su suma es menor que la suma dada.
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 program
int 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 value
import 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 Code
public 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 value def 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 Code if __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 value
using 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 Code
public 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 value
function 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 value
function 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>
Producción:
5, 1, 3 5, 1, 4 1, 3, 4 1, 3, 7
La complejidad temporal de la solución anterior es O(n 3 ).
Una solución eficiente puede imprimir trillizos en O (n 2 ) ordenando primero la array y luego usando el método 1 de esta publicación en un bucle.
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
A continuación se muestra la implementación de la idea anterior.
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 program
int 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 value
import 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 Code
public 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 value def 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 code if __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 value
using 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 Code
public 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 value
function 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>
Producción:
1, 3, 4 1, 3, 5 1, 3, 7 1, 4, 5