Cuente el número de trillizos con un producto que no exceda un número dado

Dado un entero positivo N , la tarea es encontrar el número de tripletes de enteros positivos (X, Y, Z) , cuyo producto sea como máximo N .

Ejemplos:

Entrada: N = 2
Salida: 4
Explicación: A continuación se muestran los tripletes cuyo producto es como máximo N(= 2):

1. (1, 1, 1): El producto es 1*1*1 = 1.
2. (1, 1, 2): El producto es 1*1*2 = 2.
3. (1, 2, 1): El producto es 1*2*1 = 2.
4. (2, 1, 1): El producto es 2*1*1 = 2.

Por lo tanto, la cuenta total es 4.

Entrada: 6
Salida: 25

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los tripletes posibles cuyos valores se encuentran en el rango [0, N] y contar esos tripletes cuyo producto de valores es como máximo N . Después de verificar todos los tripletes, imprima el conteo total obtenido. 

Complejidad de Tiempo: O(N ³ )
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior también se puede optimizar generando todos los pares posibles (i, j) en el rango [1, N] e incrementando el recuento de todos los pares posibles en N / (i * j) . Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos ans , que almacene el recuento de todos los tripletes posibles.
• Genere todos los pares posibles (i, j) en el rango [1, N] y, si el producto de los pares es mayor que N , busque los siguientes pares. De lo contrario, incremente el recuento de todos los pares posibles en N/(i*j) .
• Después de completar los pasos anteriores, imprima el valor de ans como resultado.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <iostream>
using namespace std;
 
// Function to count the number of
// triplets whose product is at most N
int countTriplets(int N)
{
    // Stores the count of triplets
    int ans = 0;
 
    // Iterate over the range [0, N]
    for (int i = 1; i <= N; i++) {
 
        // Iterate over the range [0, N]
        for (int j = 1; j <= N; j++) {
 
            // If the product of
            // pairs exceeds N
            if (i * j > N)
                break;
 
            // Increment the count of
            // possible triplets
            ans += N / (i * j);
        }
    }
 
    // Return the total count
    return ans;
}
 
// Driver Code
int main()
{
    int N = 10;
    cout << countTriplets(N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to count the number of
// triplets whose product is at most N
static int countTriplets(int N)
{
     
    // Stores the count of triplets
    int ans = 0;
 
    // Iterate over the range [0, N]
    for(int i = 1; i <= N; i++)
    {
         
        // Iterate over the range [0, N]
        for(int j = 1; j <= N; j++)
        {
             
            // If the product of
            // pairs exceeds N
            if (i * j > N)
                break;
 
            // Increment the count of
            // possible triplets
            ans += N / (i * j);
        }
    }
 
    // Return the total count
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 10;
    System.out.print(countTriplets(N));
}
}
 
// This code is contributed by Amit Katiyar

# Python3 program for the above approach
 
# Function to count the number of
# triplets whose product is at most N
 
 
def countTriplets(N):
 
    # Stores the count of triplets
    ans = 0
 
    # Iterate over the range [0, N]
    for i in range(1, N + 1):
 
        # Iterate over the range [0, N]
        for j in range(1, N + 1):
 
            # If the product of
            # pairs exceeds N
            if (i * j > N):
                break
 
            # Increment the count of
            # possible triplets
            ans += N // (i * j)
 
    # Return the total count
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    N = 10
    print(countTriplets(N))
 
    # This code is contributed by ukasp.

// C# program for the above approach
using System;
 
class GFG{
 
// Function to count the number of
// triplets whose product is at most N
static int countTriplets(int N)
{
     
    // Stores the count of triplets
    int ans = 0;
 
    // Iterate over the range [0, N]
    for(int i = 1; i <= N; i++)
    {
         
        // Iterate over the range [0, N]
        for(int j = 1; j <= N; j++)
        {
             
            // If the product of
            // pairs exceeds N
            if (i * j > N)
                break;
 
            // Increment the count of
            // possible triplets
            ans += N / (i * j);
        }
    }
 
    // Return the total count
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 10;
    Console.Write(countTriplets(N));
}
}
 
// This code is contributed by Princi Singh

<script>
// JavaScript program for the above approach
 
// Function to count the number of
// triplets whose product is at most N
function countTriplets( N){
    // Stores the count of triplets
    let ans = 0;
    // Iterate over the range [0, N]
    for (let i = 1; i <= N; i++) {
 
        // Iterate over the range [0, N]
        for (let j = 1; j <= N; j++) {
 
            // If the product of
            // pairs exceeds N
            if (i * j > N)
                break;
 
            // Increment the count of
            // possible triplets
            ans += Math.floor(N / (i * j));
        }
    }
 
    // Return the total count
    return ans;
}
 
// Driver Code
 
let N = 10;
document.write( countTriplets(N));
 
// This code is contributed by rohitsingh07052.
</script>

53

Complejidad Temporal: O(N ² )
Espacio Auxiliar: O(1), ya que no se ha tomado ningún espacio extra.