Dada una array de enteros distintos y un valor de suma. Encuentre el recuento de trillizos con una suma menor que el valor de suma dado. La Complejidad Temporal esperada es O(n 2 ).
Ejemplos:
Input : arr[] = {-2, 0, 1, 3}
sum = 2.
Output : 2
Explanation : Below are triplets with sum less than 2
(-2, 0, 1) and (-2, 0, 3)
Input : arr[] = {5, 1, 3, 4, 7}
sum = 12.
Output : 4
Explanation : Below are triplets with sum less than 12
(1, 3, 4), (1, 3, 5), (1, 3, 7) and
(1, 4, 5)
C++
// A Simple C++ program to count triplets with sum smaller
// than a given value
#include <bits/stdc++.h>
using namespace std;
int countTriplets(int arr[], int n, int sum)
{
// 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] < sum)
ans++;
}
}
return ans;
}
// Driver program
int main()
{
int arr[] = { 5, 1, 3, 4, 7 };
int n = sizeof arr / sizeof arr[0];
int sum = 12;
cout << countTriplets(arr, n, sum) << endl;
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// A Simple C program to count triplets with sum smaller
// than a given value
#include <stdio.h>
int countTriplets(int arr[], int n, int sum)
{
// 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] < sum)
ans++;
}
}
return ans;
}
// Driver program
int main()
{
int arr[] = { 5, 1, 3, 4, 7 };
int n = sizeof arr / sizeof arr[0];
int sum = 12;
printf("%d\n", countTriplets(arr, n, sum));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// A Simple Java program to count triplets with sum smaller
// than a given value
class Test
{
static int arr[] = new int[]{5, 1, 3, 4, 7};
static int countTriplets(int n, int sum)
{
// 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] < sum)
ans++;
}
}
return ans;
}
// Driver method to test the above function
public static void main(String[] args)
{
int sum = 12;
System.out.println(countTriplets(arr.length, sum));
}
}
Python 3
# A Simple Python 3 program to count triplets with sum smaller # than a given value #include<bits/stdc++.h> def countTriplets(arr, n, sum): # 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] < sum): ans+=1 return ans # Driver program arr = [5, 1, 3, 4, 7] n = len(arr) sum = 12 print(countTriplets(arr, n, sum)) #Contributed by Smitha
C#
// A Simple C# program to count triplets with sum smaller
// than a given value
using System;
class Test
{
static int[] arr = new int[]{5, 1, 3, 4, 7};
static int countTriplets(int n, int sum)
{
// 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] < sum)
ans++;
}
}
return ans;
}
// Driver method to test the above function
public static void Main()
{
int sum = 12;
Console.Write(countTriplets(arr.Length, sum));
}
}
Javascript
<script>
// A Simple Javascript program to count triplets with sum smaller
// than a given value
let arr = [5, 1, 3, 4, 7];
function countTriplets(n,sum)
{
// Initialize result
let ans = 0;
// 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)
ans++;
}
}
return ans;
}
// Driver method to test the above function
let sum = 12;
document.write(countTriplets(arr.length, sum));
// This code is contributed by avanitrachhadiya2155
</script>
C++
// C++ program to count triplets with sum smaller than a given value
#include<bits/stdc++.h>
using namespace std;
int countTriplets(int arr[], int n, int sum)
{
// Sort input array
sort(arr, arr+n);
// Initialize result
int ans = 0;
// 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
// can be total k-j third elements.
ans += (k - j);
j++;
}
}
}
return ans;
}
// Driver program
int main()
{
int arr[] = {5, 1, 3, 4, 7};
int n = sizeof arr / sizeof arr[0];
int sum = 12;
cout << countTriplets(arr, n, sum) << endl;
return 0;
}
Java
// A Simple Java program to count triplets with sum smaller
// than a given value
import java.util.Arrays;
class Test
{
static int arr[] = new int[]{5, 1, 3, 4, 7};
static int countTriplets(int n, int sum)
{
// Sort input array
Arrays.sort(arr);
// Initialize result
int ans = 0;
// 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
// can be total k-j third elements.
ans += (k - j);
j++;
}
}
}
return ans;
}
// Driver method to test the above function
public static void main(String[] args)
{
int sum = 12;
System.out.println(countTriplets(arr.length, sum));
}
}
Python3
# Python3 program to count triplets with # sum smaller than a given value # Function to count triplets with sum smaller # than a given value def countTriplets(arr,n,sum): # Sort input array arr.sort() # Initialize result ans = 0 # Every iteration of loop counts triplet with # first element as arr[i]. 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): # 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 = k-1 # Else move left corner else: # This is important. For current i and j, there # can be total k-j third elements. ans += (k - j) j = j+1 return ans # Driver program if __name__=='__main__': arr = [5, 1, 3, 4, 7] n = len(arr) sum = 12 print(countTriplets(arr, n, sum)) # This code is contributed by # Yatin Gupta
C#
// A Simple C# program to count
// triplets with sum smaller
// than a given value
using System;
class GFG
{
static int []arr = new int[]{5, 1, 3, 4, 7};
static int countTriplets(int n, int sum)
{
// Sort input array
Array.Sort(arr);
// Initialize result
int ans = 0;
// 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
// can be total k-j third elements.
ans += (k - j);
j++;
}
}
}
return ans;
}
// Driver Code
public static void Main()
{
int sum = 12;
Console.Write(countTriplets(arr.Length, sum));
}
}
// This code is contributed by Smitha
Javascript
<script>
// A Simple Javascript program to count triplets with sum smaller
// than a given value
let arr = [5, 1, 3, 4, 7];
function countTriplets(n,sum)
{
// Sort input array
arr.sort(function(a,b){return b-a});
// Initialize result
let ans = 0;
// 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
// can be total k-j third elements.
ans += (k - j);
j++;
}
}
}
return ans;
}
// Driver method to test the above function
let sum = 12;
document.write(countTriplets(arr.length, sum));
// This code is contributed by rag2127
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA