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