Dada una array de enteros distintos y un rango [a, b], la tarea es contar el número de tripletes que tienen una suma en el rango [a, b].
Ejemplos:
Input : arr[] = {8, 3, 5, 2}
range = [7, 11]
Output : 1
There is only one triplet {2, 3, 5}
having sum 10 in range [7, 11].
Input : arr[] = {2, 7, 5, 3, 8, 4, 1, 9}
range = [8, 16]
Output : 36
Un enfoque ingenuo es ejecutar tres bucles para considerar todos los tripletes uno por uno. Encuentre la suma de cada triplete e incremente el conteo si la suma se encuentra en un rango dado [a, b].
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count triplets with
// sum that lies in given range [a, b].
#include <bits/stdc++.h>
using namespace std;
// Function to count triplets
int countTriplets(int arr[], int n, int a, int b)
{
// Initialize result
int ans = 0;
// 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] >= a
&& arr[i] + arr[j] + arr[k] <= b)
ans++;
}
}
return ans;
}
// Driver Code
int main()
{
int arr[] = { 2, 7, 5, 3, 8, 4, 1, 9 };
int n = sizeof arr / sizeof arr[0];
int a = 8, b = 16;
cout << countTriplets(arr, n, a, b) << endl;
return 0;
}
Java
// Java program to count triplets
// with sum that lies in given
// range [a, b].
import java.util.*;
class GFG
{
// Function to count triplets
public static int countTriplets(int []arr, int n,
int a, int b)
{
// Initialize result
int ans = 0;
// 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] >= a &&
arr[i] + arr[j] + arr[k] <= b)
{ans++;}
}
}
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 2, 7, 5, 3, 8, 4, 1, 9 };
int n = arr.length;
int a = 8, b = 16;
System.out.println("" + countTriplets(arr, n,
a, b));
}
}
// This code is contributed
// by Harshit Saini
Python3
# Python3 program to count # triplets with sum that # lies in given range [a, b]. # Function to count triplets def countTriplets(arr, n, a, b): # Initialize result ans = 0 # Fix the first # element as A[i] for i in range(0, n - 2): # Fix the second # element as A[j] for j in range(i + 1, n - 1): # Now look for # the third number for k in range(j + 1, n): if ((arr[i] + arr[j] + arr[k] >= a) and (arr[i] + arr[j] + arr[k] <= b)): ans += 1 return ans # Driver code if __name__ == "__main__": arr = [ 2, 7, 5, 3, 8, 4, 1, 9 ] n = len(arr) a = 8; b = 16 print(countTriplets(arr, n, a, b)) # This code is contributed # by Harshit Saini
C#
// C# program to count triplets
// with sum that lies in given
// range [a, b].
using System;
class GFG
{
// Function to count triplets
public static int countTriplets(int []arr, int n,
int a, int b)
{
// Initialize result
int ans = 0;
// 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] >= a &&
arr[i] + arr[j] + arr[k] <= b)
{ans++;}
}
}
}
return ans;
}
// Driver Code
public static void Main()
{
int[] arr = {2, 7, 5, 3, 8, 4, 1, 9};
int n = arr.Length;
int a = 8, b = 16;
Console.WriteLine("" + countTriplets(arr, n,
a, b));
}
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
PHP
<?php
// PHP program to count triplets with
// sum that lies in given range [a, b].
// Function to count triplets
function countTriplets($arr, $n, $a, $b)
{
// Initialize result
$ans = 0;
// 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] >= $a &&
$arr[$i] + $arr[$j] + $arr[$k] <= $b)
$ans++;
}
}
return $ans;
}
// Driver Code
$arr = array( 2, 7, 5, 3, 8, 4, 1, 9 );
$n = sizeof($arr);
$a = 8; $b = 16;
echo countTriplets($arr, $n, $a, $b) . "\n";
// This code is contributed
// by Akanksha Rai(Abby_akku)
?>
Javascript
<script>
// Javascript program to count triplets with
// sum that lies in given range [a, b].
// Function to count triplets
function countTriplets( arr, n, a, b)
{
// Initialize result
var ans = 0;
// Fix the first element as A[i]
for (var i = 0; i < n - 2; i++) {
// Fix the second element as A[j]
for (var j = i + 1; j < n - 1; j++) {
// Now look for the third number
for (var k = j + 1; k < n; k++)
if (arr[i] + arr[j] + arr[k] >= a
&& arr[i] + arr[j] + arr[k] <= b)
ans++;
}
}
return ans;
}
// Driver Code
var arr = [ 2, 7, 5, 3, 8, 4, 1, 9 ];
var n = arr.length;
var a = 8, b = 16;
document.write( countTriplets(arr, n, a, b) );
</script>
Producción:
36
Complejidad temporal: O(n 3 )
Espacio auxiliar: O(1)
Una solución eficiente es primero encontrar el conteo de tripletes que tienen una suma menor o igual al límite superior b en el rango [a, b]. Este conteo de tripletes también incluirá tripletes que tengan una suma menor que el límite inferior a. Resta el conteo de trillizos que tienen una suma menor que a. El resultado final es el conteo de tripletes que tienen una suma en el rango [a, b].
El algoritmo es como sigue:
- Encuentre el número de trillizos que tienen una suma menor o igual que b. Sea esta cuenta x.
- Encuentre el número de tripletes que tienen una suma menor que a. Sea esta cuenta y.
- El resultado final es xy.
Para encontrar el conteo de trillizos que tienen una suma menor o igual al valor dado, consulte Contar trillizos con una suma menor que un valor dado
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count triplets with
// sum that lies in given range [a, b].
#include <bits/stdc++.h>
using namespace std;
// Function to find count of triplets having
// sum less than or equal to val.
int countTripletsLessThan(int arr[], int n, int val)
{
// sort the input array.
sort(arr, arr + n);
// Initialize result
int ans = 0;
int j, k;
// to store sum
int sum;
// Fix the first element
for (int 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) {
sum = arr[i] + arr[j] + arr[k];
// If sum of current triplet
// is greater, then to reduce it
// decrease k.
if (sum > val)
k--;
// If sum is less than or equal
// to given value, then add
// possible triplets (k-j) to result.
else {
ans += (k - j);
j++;
}
}
}
return ans;
}
// Function to return count of triplets having
// sum in range [a, b].
int countTriplets(int arr[], int n, int a, int b)
{
// to store count of triplets.
int res;
// Find count of triplets having sum less
// than or equal to b and subtract count
// of triplets having sum less than or
// equal to a-1.
res = countTripletsLessThan(arr, n, b) -
countTripletsLessThan(arr, n, a - 1);
return res;
}
// Driver Code
int main()
{
int arr[] = { 2, 7, 5, 3, 8, 4, 1, 9 };
int n = sizeof arr / sizeof arr[0];
int a = 8, b = 16;
cout << countTriplets(arr, n, a, b) << endl;
return 0;
}
Java
// Java program to count triplets
// with sum that lies in given
// range [a, b].
import java.util.*;
class GFG
{
// Function to find count of
// triplets having sum less
// than or equal to val.
public static int countTripletsLessThan(int []arr,
int n, int val)
{
// sort the input array.
Arrays.sort(arr);
// Initialize result
int ans = 0;
int j, k;
// to store sum
int sum;
// Fix the first element
for (int 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)
{
sum = arr[i] + arr[j] + arr[k];
// If sum of current triplet
// is greater, then to reduce it
// decrease k.
if (sum > val)
k--;
// If sum is less than or
// equal to given value,
// then add possible
// triplets (k-j) to result.
else
{
ans += (k - j);
j++;
}
}
}
return ans;
}
// Function to return count
// of triplets having sum
// in range [a, b].
public static int countTriplets(int arr[], int n,
int a, int b)
{
// to store count
// of triplets.
int res;
// Find count of triplets
// having sum less than or
// equal to b and subtract
// count of triplets having
// sum less than or equal
// to a-1.
res = countTripletsLessThan(arr, n, b) -
countTripletsLessThan(arr, n, a - 1);
return res;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = {2, 7, 5, 3,
8, 4, 1, 9};
int n = arr.length;
int a = 8, b = 16;
System.out.println("" + countTriplets(arr, n,
a, b));
}
}
// This code is contributed
// by Harshit Saini
Python3
# Python program to count # triplets with sum that # lies in given range [a, b]. # Function to find count of # triplets having sum less # than or equal to val. def countTripletsLessThan(arr, n, val): # sort the input array. arr.sort() # Initialize result ans = 0 j = 0; k = 0 # to store sum sum = 0 # Fix the first element for i in range(0,n-2): # 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 : sum = arr[i] + arr[j] + arr[k] # If sum of current triplet # is greater, then to reduce it # decrease k. if sum > val: k-=1 # If sum is less than or # equal to given value, # then add possible # triplets (k-j) to result. else : ans += (k - j) j += 1 return ans # Function to return # count of triplets having # sum in range [a, b]. def countTriplets(arr, n, a, b): # to store count of triplets. res = 0 # Find count of triplets # having sum less than or # equal to b and subtract # count of triplets having # sum less than or equal to a-1. res = (countTripletsLessThan(arr, n, b) - countTripletsLessThan(arr, n, a - 1)) return res # Driver code if __name__ == "__main__": arr = [ 2, 7, 5, 3, 8, 4, 1, 9 ] n = len(arr) a = 8; b = 16 print(countTriplets(arr, n, a, b)) # This code is contributed by # Harshit Saini
C#
// C# program to count triplets
// with sum that lies in given
// range [a, b].
using System;
class GFG
{
// Function to find count of
// triplets having sum less
// than or equal to val.
public static int countTripletsLessThan(int[] arr,
int n, int val)
{
// sort the input array.
Array.Sort(arr);
// Initialize result
int ans = 0;
int j, k;
// to store sum
int sum;
// Fix the first element
for (int 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)
{
sum = arr[i] + arr[j] + arr[k];
// If sum of current triplet
// is greater, then to reduce it
// decrease k.
if (sum > val)
k--;
// If sum is less than or
// equal to given value,
// then add possible
// triplets (k-j) to result.
else
{
ans += (k - j);
j++;
}
}
}
return ans;
}
// Function to return count
// of triplets having sum
// in range [a, b].
public static int countTriplets(int[] arr, int n,
int a, int b)
{
// to store count
// of triplets.
int res;
// Find count of triplets
// having sum less than or
// equal to b and subtract
// count of triplets having
// sum less than or equal
// to a-1.
res = countTripletsLessThan(arr, n, b) -
countTripletsLessThan(arr, n, a - 1);
return res;
}
// Driver Code
public static void Main()
{
int[] arr = {2, 7, 5, 3,
8, 4, 1, 9};
int n = arr.Length;
int a = 8, b = 16;
Console.WriteLine("" + countTriplets(arr, n,
a, b));
}
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
PHP
<?php
// PHP program to count triplets with
// sum that lies in given range [a, b].
// Function to find count of triplets
// having sum less than or equal to val.
function countTripletsLessThan($arr, $n, $val)
{
// sort the input array.
sort($arr);
// Initialize result
$ans = 0;
// to store sum
$sum;
// Fix the first element
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)
{
$sum = $arr[$i] + $arr[$j] + $arr[$k];
// If sum of current triplet is greater,
// then to reduce it decrease k.
if ($sum > $val)
$k--;
// If sum is less than or equal
// to given value, then add possible
// triplets (k-j) to result.
else
{
$ans += ($k - $j);
$j++;
}
}
}
return $ans;
}
// Function to return count of triplets
// having sum in range [a, b].
function countTriplets($arr, $n, $a, $b)
{
// to store count of triplets.
$res;
// Find count of triplets having sum less
// than or equal to b and subtract count
// of triplets having sum less than or
// equal to a-1.
$res = countTripletsLessThan($arr, $n, $b) -
countTripletsLessThan($arr, $n, $a - 1);
return $res;
}
// Driver Code
$arr = array( 2, 7, 5, 3, 8, 4, 1, 9 );
$n = sizeof($arr);
$a = 8;
$b = 16;
echo countTriplets($arr, $n, $a, $b), "\n";
// This code is contributed by Sachin
?>
Javascript
<script>
// JavaScript program to count triplets
// with sum that lies in given
// range [a, b].
// Function to find count of
// triplets having sum less
// than or equal to val.
function countTripletsLessThan(arr, n, val) {
// sort the input array.
arr.sort();
// Initialize result
var ans = 0;
var j, k;
// to store sum
var sum;
// Fix the first element
for (var 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) {
sum = arr[i] + arr[j] + arr[k];
// If sum of current triplet
// is greater, then to reduce it
// decrease k.
if (sum > val) k--;
// If sum is less than or
// equal to given value,
// then add possible
// triplets (k-j) to result.
else {
ans += k - j;
j++;
}
}
}
return ans;
}
// Function to return count
// of triplets having sum
// in range [a, b].
function countTriplets(arr, n, a, b) {
// to store count
// of triplets.
var res;
// Find count of triplets
// having sum less than or
// equal to b and subtract
// count of triplets having
// sum less than or equal
// to a-1.
res =
countTripletsLessThan(arr, n, b) -
countTripletsLessThan(arr, n, a - 1);
return res;
}
// Driver Code
var arr = [2, 7, 5, 3, 8, 4, 1, 9];
var n = arr.length;
var a = 8,
b = 16;
document.write("" + countTriplets(arr, n, a, b));
</script>
Producción:
36
Complejidad temporal: O(n 2 )
Espacio auxiliar: O(1)