Dado un entero positivo N , la tarea es encontrar el número de tripletes (A, B, C) de los primeros N Números Naturales tales que A * B * C ≤ N .
Ejemplos:
Entrada: N = 3
Salida: 4
Explicación:
Los siguientes son los tripletes que satisfacen los criterios dados:
- ( 1, 1, 1 ) => 1 * 1 * 1 = 1 ≤ 2.
- ( 1, 1, 2 ) => 1 * 1 * 2 = 2 ≤ 2.
- ( 1, 2, 1 ) => 1 * 2 * 1 = 2 ≤ 2.
- ( 2, 1, 1 ) => 2 * 1 * 1 = 2 ≤ 2.
Por lo tanto, el conteo total de trillizos es 4.
Entrada: N = 10
Salida: 53
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los tripletes posibles a partir de los primeros N números naturales y contar esos tripletes que satisfacen los criterios dados. Después de verificar todos los tripletes, imprima el conteo total obtenido.
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior puede optimizarse mediante la observación de que si A y B son fijos, entonces es posible calcular todas las opciones posibles para C haciendo N /(A*B) porque N/(A*B) dé el valor máximo, digamos X , que al multiplicar con (A*B) da como resultado un valor menor o igual que N . Entonces, todas las opciones posibles de C serán de 1 a X. Ahora, A y B pueden arreglarse probando A para cada número posible hasta N , yB para cada número posible hasta (N/A) . Siga los pasos a continuación para resolver el problema dado:
- Inicialice la variable, diga cnt como 0 que almacena el recuento de tripletes posibles.
- Iterar un ciclo sobre el rango [1, N] usando la variable i e iterar anidado sobre el rango [1, N] usando la variable j e incrementar el valor de cnt por el valor de cnt/(i*j) .
- Después de completar los pasos anteriores, imprima el valor de cnt como resultado.
A continuación se muestra la implementación del enfoque:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find number of triplets // (A, B, C) having A * B * C <= N int countTriplets(int N) { // Stores the count of triplets int cnt = 0; // Iterate a loop fixing the value // of A for (int A = 1; A <= N; ++A) { // Iterate a loop fixing the // value of A for (int B = 1; B <= N / A; ++B) { // Find the total count of // triplets and add it to cnt cnt += N / (A * B); } } // Return the total triplets formed return cnt; } // Driver Code int main() { int N = 2; cout << countTriplets(N); return 0; }
Java
// Java program for the above approach import java.io.*; class GFG { // Function to find number of triplets // (A, B, C) having A * B * C <= N static int countTriplets(int N) { // Stores the count of triplets int cnt = 0; // Iterate a loop fixing the value // of A for (int A = 1; A <= N; ++A) { // Iterate a loop fixing the // value of A for (int B = 1; B <= N / A; ++B) { // Find the total count of // triplets and add it to cnt cnt += N / (A * B); } } // Return the total triplets formed return cnt; } // Driver Code public static void main(String[] args) { int N = 2; System.out.println(countTriplets(N)); } } // This code is contributed by dwivediyash
Python3
# Python3 program for the above approach # Function to find number of triplets # (A, B, C) having A * B * C <= N def countTriplets(N) : # Stores the count of triplets cnt = 0; # Iterate a loop fixing the value # of A for A in range( 1, N + 1) : # Iterate a loop fixing the # value of A for B in range(1, N // A + 1) : # Find the total count of # triplets and add it to cnt cnt += N // (A * B); # Return the total triplets formed return cnt; # Driver Code if __name__ == "__main__" : N = 2; print(countTriplets(N)); # This code is contributed by AnkThon
C#
// C# program for the above approach using System; public class GFG { // Function to find number of triplets // (A, B, C) having A * B * C <= N static int countTriplets(int N) { // Stores the count of triplets int cnt = 0; // Iterate a loop fixing the value // of A for (int A = 1; A <= N; ++A) { // Iterate a loop fixing the // value of A for (int B = 1; B <= N / A; ++B) { // Find the total count of // triplets and add it to cnt cnt += N / (A * B); } } // Return the total triplets formed return cnt; } // Driver Code public static void Main(string[] args) { int N = 2; Console.WriteLine(countTriplets(N)); } } // This code is contributed by AnkThon
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find number of triplets // (A, B, C) having A * B * C <= N function countTriplets(N) { // Stores the count of triplets let cnt = 0; // Iterate a loop fixing the value // of A for (let A = 1; A <= N; ++A) { // Iterate a loop fixing the // value of A for (let B = 1; B <= N / A; ++B) { // Find the total count of // triplets and add it to cnt cnt += N / (A * B); } } // Return the total triplets formed return cnt; } // Driver Code let N = 2; document.write(countTriplets(N)); // This code is contributed by Potta Lokesh </script>
4
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rakeshsahni y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA