Dados dos números enteros L y R , la tarea es encontrar el número de tripletes únicos cuyos valores se encuentran en el rango [L, R] , tal que la suma de dos números cualquiera sea igual al tercer número.
Ejemplos:
Entrada: L = 1, R = 3
Salida: 3
Explicación: Tres de esos tripletes que satisfacen las condiciones necesarias son (1, 1, 2), (1, 2, 3) y (2, 1, 3).Entrada: L = 2, R = 6
Salida: 6
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los tripletes posibles en el rango [L, R] y contar esos tripletes que tienen la suma de dos números cualquiera del par igual al tercer número. Después de verificar todos los tripletes, imprima el conteo total obtenido.
Complejidad de Tiempo: O((R – L) 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:
- Si la diferencia entre el rango dado es menor que L , entonces no existe tal triplete que tenga la suma de dos números igual al tercer número.
- Si la diferencia entre el rango dado es al menos L , entonces (R – L) se encuentra en el rango L y R , es decir, {L, (R – L), R} . Se puede observar que la suma de L y cualquier otro número en el rango [L, R – L] es como máximo R .
- Por lo tanto, el número total de posibles tripletas válidas, donde el primer elemento es L viene dado por (R – L – L + 1) .
- De manera similar, cuando el primer elemento es (L + 1) , entonces el número de tripletes es (R – L – L) , y así sucesivamente.
De las observaciones anteriores, el número total de tripletes forma un AP con los términos (R – L – L + 1), (R – L – L), (R – L – L – 1), ……… que consta de ( R – L – L + 1) número de términos. Por lo tanto, el número total de trillizos viene dado por:
donde, N es (R – L – L + 1)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the number of triplets // from the range [L, R] having sum of two // numbers from the triplet equal to the third number int totalCombination(int L, int R) { // Stores the total number of triplets int count = 0; // Find the difference of the range int K = R - L; // Case 1: If triplets can't // be formed, then return 0 if (K < L) return 0; // Otherwise int ans = K - L; // Update the total number of triplets count = ((ans + 1) * (ans + 2)) / 2; // Return the count return count; } // Driver Code int main() { int L = 2, R = 6; cout << totalCombination(L, R); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find the number of triplets // from the range [L, R] having sum of two // numbers from the triplet equal to the third number static int totalCombination(int L, int R) { // Stores the total number of triplets int count = 0; // Find the difference of the range int K = R - L; // Case 1: If triplets can't // be formed, then return 0 if (K < L) return 0; // Otherwise int ans = K - L; // Update the total number of triplets count = ((ans + 1) * (ans + 2)) / 2; // Return the count return count; } // Driven Code public static void main(String[] args) { int L = 2, R = 6; System.out.print(totalCombination(L, R)); } } // This code is contributed by susmitakundugoaldanga.
Python3
# Python3 program for the above approach # Function to find the number of triplets # from the range [L, R] having sum of two # numbers from the triplet equal to the third number def totalCombination(L, R): # Stores the total number of triplets count = 0 # Find the difference of the range K = R - L # Case 1: If triplets can't # be formed, then return 0 if (K < L): return 0 # Otherwise ans = K - L # Update the total number of triplets count = ((ans + 1) * (ans + 2)) // 2 # Return the count return count # Driver Code if __name__ == '__main__': L, R = 2, 6 print (totalCombination(L, R)) # This code is contributed by mohit kumar 29.
C#
// C# program to implement // the above approach using System; class GFG { // Function to find the number of triplets // from the range [L, R] having sum of two // numbers from the triplet equal to the third number static int totalCombination(int L, int R) { // Stores the total number of triplets int count = 0; // Find the difference of the range int K = R - L; // Case 1: If triplets can't // be formed, then return 0 if (K < L) return 0; // Otherwise int ans = K - L; // Update the total number of triplets count = ((ans + 1) * (ans + 2)) / 2; // Return the count return count; } // Driver Code public static void Main() { int L = 2, R = 6; Console.WriteLine(totalCombination(L, R)); } } // This code is contributed by sauravghosh0416.
Javascript
<script> // Javascript program for the above approach // Function to find the number of triplets // from the range [L, R] having sum of two // numbers from the triplet equal to the third number function totalCombination(L, R) { // Stores the total number of triplets let count = 0; // Find the difference of the range let K = R - L; // Case 1: If triplets can't // be formed, then return 0 if (K < L) return 0; // Otherwise let ans = K - L; // Update the total number of triplets count = ((ans + 1) * (ans + 2)) / 2; // Return the count return count; } let L = 2, R = 6; document.write(totalCombination(L, R)); </script>
6
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por abhijeet010304 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA