Cuente tripletes tales que el producto de dos números sumados con el tercero sea N

Posted on by Rudeus Greyrat

Dado un número entero positivo N , la tarea es encontrar el número de tripletes (A, B, C) donde A , B , C son números enteros positivos tales que el producto de dos números sumados con el tercer número es N , es decir, A * B + C = norte .

Ejemplos:

Entrada: N = 3
Salida: 3
Explicación:
Los siguientes son los posibles tripletes que satisfacen los criterios dados:

  1. (1, 1, 2): El valor de 1*1 + 2 = 3.
  2. (1, 2, 1): El valor de 1*2 + 1 = 3.
  3. (2, 1, 1): El valor de 2*1 + 1 = 3.

Por lo tanto, la cuenta total de tales trillizos es 3.

Entrada: N = 5
Salida: 8

Enfoque: El problema dado se puede resolver reorganizando la ecuación A * B + C = N como A * B = N – C . Ahora, los únicos valores posibles que A y B pueden tener para satisfacer la ecuación anterior son los divisores de N – C. Por ejemplo, si el valor de N – C = 18 , con 6 divisores que son 1, 2, 3, 6, 9, 18. Entonces, los valores de A, B que satisfacen la ecuación anterior son: (1, 18), ( 2, 9), (3, 6), (6, 3), (9, 2), (18, 1) . Entonces, para el valor de N – C = 18 , los posibles valores de A , B son 6 , es decir, el número de divisores de N – C (= 18). Siga los pasos a continuación para resolver el problema dado:

  • Inicialice una variable, digamos contar como 0 que almacena el recuento total de posibles tripletas.
  • Itere un ciclo sobre el rango [1, N – 1] usando la variable i y para cada valor, encuentro el recuento total de divisores de (N – i) y lo agrego a la variable count .
  • Después de completar los pasos anteriores, imprima el valor de count como el número resultante de tripletes.

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 divisors of
// the number (N - i)
int countDivisors(int n)
{
    // Stores the resultant count of
    // divisors of (N - i)
    int divisors = 0;
    int i;
 
    // Iterate over range [1, sqrt(N)]
    for (i = 1; i * i < n; i++) {
        if (n % i == 0) {
            divisors++;
        }
    }
    if (i - (n / i) == 1) {
        i--;
    }
    for (; i >= 1; i--) {
        if (n % i == 0) {
            divisors++;
        }
    }
    // Return the total divisors
    return divisors;
}
 
// Function to find the number of triplets
// such that A * B - C = N
int possibleTriplets(int N)
{
    int count = 0;
 
    // Loop to fix the value of C
    for (int i = 1; i < N; i++) {
 
        // Adding the number of
        // divisors in count
        count += countDivisors(N - i);
    }
 
    // Return count of triplets
    return count;
}
 
// Driver Code
int main()
{
    int N = 10;
    cout << possibleTriplets(N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
class GFG
{
   
      // Function to find the divisors of
    // the number (N - i)
    static int countDivisors(int n)
    {
       
        // Stores the resultant count of
        // divisors of (N - i)
        int divisors = 0;
        int i;
 
        // Iterate over range [1, sqrt(N)]
        for (i = 1; i * i < n; i++) {
            if (n % i == 0) {
                divisors++;
            }
        }
        if (i - (n / i) == 1) {
            i--;
        }
        for (; i >= 1; i--) {
            if (n % i == 0) {
                divisors++;
            }
        }
 
        // Return the total divisors
        return divisors;
    }
 
    // Function to find the number of triplets
    // such that A * B - C = N
    static int possibleTriplets(int N)
    {
        int count = 0;
 
        // Loop to fix the value of C
        for (int i = 1; i < N; i++) {
 
            // Adding the number of
            // divisors in count
            count += countDivisors(N - i);
        }
 
        // Return count of triplets
        return count;
    }
 
    // Driver Code
    public static void main (String[] args) {
       
        int N = 10;
        System.out.println(possibleTriplets(N));
    }
}
 
// This code is contributed by Dharanendra L V.

Python3

# Python program for the above approach
import math
 
# function to find the divisors of
# the number (N - i)
def countDivisors(n):
 
    # Stores the resultant count of
    # divisors of (N - i)
    divisors = 0
 
    # Iterate over range [1, sqrt(N)]
    for i in range(1, math.ceil(math.sqrt(n))+1):
        if n % i == 0:
            divisors = divisors+1
 
        if (i - (n / i) == 1):
            i = i-1
 
    for i in range(math.ceil(math.sqrt(n))+1, 1, -1):
        if (n % i == 0):
            divisors = divisors+1
 
     # Return the total divisors
    return divisors
 
    # def to find the number of triplets
    # such that A * B - C = N
 
 
def possibleTriplets(N):
    count = 0
 
    # Loop to fix the value of C
    for i in range(1, N):
 
        # Adding the number of
        # divisors in count
        count = count + countDivisors(N - i)
 
        # Return count of triplets
    return count
 
    # Driver Code
# Driver Code
if __name__ == "__main__":
    N = 10
    print(possibleTriplets(N))
 
# This code is contributed by Potta Lokesh

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the divisors of
// the number (N - i)
static int countDivisors(int n)
{
    // Stores the resultant count of
    // divisors of (N - i)
    int divisors = 0;
    int i;
 
    // Iterate over range [1, sqrt(N)]
    for (i = 1; i * i < n; i++) {
        if (n % i == 0) {
            divisors++;
        }
    }
    if (i - (n / i) == 1) {
        i--;
    }
    for (; i >= 1; i--) {
        if (n % i == 0) {
            divisors++;
        }
    }
    // Return the total divisors
    return divisors;
}
 
// Function to find the number of triplets
// such that A * B - C = N
static int possibleTriplets(int N)
{
    int count = 0;
 
    // Loop to fix the value of C
    for (int i = 1; i < N; i++) {
 
        // Adding the number of
        // divisors in count
        count += countDivisors(N - i);
    }
 
    // Return count of triplets
    return count;
}
 
// Driver Code
public static void Main()
{
    int N = 10;
    Console.Write(possibleTriplets(N));
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

Javascript

<script>
// javascript program for the above approach
      // Function to find the divisors of
    // the number (N - i)
    function countDivisors(n)
    {
       
        // Stores the resultant count of
        // divisors of (N - i)
        var divisors = 0;
        var i;
 
        // Iterate over range [1, sqrt(N)]
        for (i = 1; i * i < n; i++) {
            if (n % i == 0) {
                divisors++;
            }
        }
        if (i - (n / i) == 1) {
            i--;
        }
        for (; i >= 1; i--) {
            if (n % i == 0) {
                divisors++;
            }
        }
 
        // Return the total divisors
        return divisors;
    }
 
    // Function to find the number of triplets
    // such that A * B - C = N
    function possibleTriplets(N)
    {
        var count = 0;
 
        // Loop to fix the value of C
        for (var i = 1; i < N; i++) {
 
            // Adding the number of
            // divisors in count
            count += countDivisors(N - i);
        }
 
        // Return count of triplets
        return count;
    }
 
    // Driver Code
    var N = 10;
    document.write(possibleTriplets(N));
 
// This code is contributed by shikhasingrajput
</script>
Producción: 

23

 

Complejidad de tiempo: O(N*sqrt(N))
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por div3yansh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *