Encuentre la suma máxima (a+b) para un número entero de entrada N que satisfaga la condición dada

Dado un número entero N , la tarea es encontrar la suma más grande ( a + b ) {1 ≤ a ≤ N, 1 ≤ b ≤ N} tal que a * b/(a + b) sea un número entero (es decir, a + b divide a * b) y a != b. 

Ejemplos:  

Entrada: N = 10 
Salida: 9 
Explicación:  Los números a = 3 y b = 6 conducen a suma = 9 también 6 * 3 = 18 que es divisible por 6 + 3 = 9
 

Entrada: N = 20 
Salida: 27 

Enfoque ingenuo: la idea para resolver este problema con el enfoque ingenuo es utilizar el concepto de bucles anidados . Se pueden seguir los siguientes pasos para calcular el resultado: 
 

1. Ejecute un ciclo anidado de 1 a N.
2. Para cada número a en el rango [1, N], encuentre otro entero b tal que a != b y ( a + b ) divida a * b .
3. Si se cumple la condición, el valor de ( a + b ) se almacena en una variable para llevar la cuenta del valor máximo obtenido.
4. Finalmente, se devuelve el valor máximo de ( a + b ).

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

// C++ implementation to find the largest value
// of a + b satisfying the given condition
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum sum of
// a + b satisfying the given condition
int getLargestSum(int N)
{
    // Initialize max_sum
    int max_sum = 0;
 
    // Consider all the possible pairs
    for (int i = 1; i <= N; i++) {
        for (int j = i + 1; j <= N; j++) {
 
            // Check if the product is
            // divisible by the sum
            if (i * j % (i + j) == 0)
 
                // Storing the maximum sum
                // in the max_sum variable
                max_sum = max(max_sum, i + j);
        }
    }
 
    // Return the max_sum value
    return max_sum;
}
 
// Driver code
int main()
{
    int N = 25;
 
    int max_sum = getLargestSum(N);
 
    cout << max_sum << endl;
    return 0;
}

// Java implementation to find the largest value
// of a + b satisfying the given condition
import java.util.*;
  
class GFG{
   
// Function to return the maximum sum of
// a + b satisfying the given condition
static int getLargestSum(int N)
{
    // Initialize max_sum
    int max_sum = 0;
 
    // Consider all the possible pairs
    for (int i = 1; i <= N; i++) {
        for (int j = i + 1; j <= N; j++) {
 
            // Check if the product is
            // divisible by the sum
            if (i * j % (i + j) == 0)
 
                // Storing the maximum sum
                // in the max_sum variable
                max_sum = Math.max(max_sum, i + j);
        }
    }
 
    // Return the max_sum value
    return max_sum;
}
 
// Driver code
public static void main(String[] args)
{
    int N = 25;
 
    int max_sum = getLargestSum(N);
 
    System.out.print(max_sum );
}
}
 
// This code is contributed by shivanisinghss2110

# Python3 implementation to find the largest value
# of a + b satisfying the given condition
 
# Function to return the maximum sum of
# a + b satisfying the given condition
def getLargestSum(N):
    # Initialize max_sum
    max_sum = 0
 
    # Consider all the possible pairs
    for i in range(1,N+1):
        for j in range(i + 1, N + 1, 1):
 
            # Check if the product is
            # divisible by the sum
            if (i * j % (i + j) == 0):
 
                # Storing the maximum sum
                # in the max_sum variable
                max_sum = max(max_sum, i + j)
 
    # Return the max_sum value
    return max_sum
 
# Driver code
if __name__ == '__main__':
    N = 25
 
    max_sum = getLargestSum(N)
    print(max_sum)
 
# This code is contributed by Surendra_Gangwar

// C# implementation to find the largest value
// of a + b satisfying the given condition
using System;
 
class GFG{
     
    // Function to return the maximum sum of
    // a + b satisfying the given condition
    static int getLargestSum(int N)
    {
        // Initialize max_sum
        int max_sum = 0;
     
        // Consider all the possible pairs
        for (int i = 1; i <= N; i++) {
            for (int j = i + 1; j <= N; j++) {
     
                // Check if the product is
                // divisible by the sum
                if (i * j % (i + j) == 0)
     
                    // Storing the maximum sum
                    // in the max_sum variable
                    max_sum = Math.Max(max_sum, i + j);
            }
        }
     
        // Return the max_sum value
        return max_sum;
    }
     
    // Driver code
    public static void Main(string[] args)
    {
        int N = 25;
     
        int max_sum = getLargestSum(N);
     
        Console.WriteLine(max_sum );
    }
}
 
// This code is contributed by AnkitRai01

<script>
// javascript implementation to find the largest value
// of a + b satisfying the given condition
 
    // Function to return the maximum sum of
    // a + b satisfying the given condition
    function getLargestSum(N) {
        // Initialize max_sum
        var max_sum = 0;
 
        // Consider all the possible pairs
        for (i = 1; i <= N; i++) {
            for (j = i + 1; j <= N; j++) {
 
                // Check if the product is
                // divisible by the sum
                if (i * j % (i + j) == 0)
 
                    // Storing the maximum sum
                    // in the max_sum variable
                    max_sum = Math.max(max_sum, i + j);
            }
        }
 
        // Return the max_sum value
        return max_sum;
    }
 
    // Driver code
     
        var N = 25;
 
        var max_sum = getLargestSum(N);
 
        document.write(max_sum);
 
// This code contributed by aashish1995
</script>

36

Complejidad de tiempo: Dado que el bucle for anidado se ejecuta (N * (N + 1)) / 2 veces, la complejidad de tiempo de la solución anterior es O(N ² ) .

Espacio Auxiliar: O(1)
Enfoque Eficiente: Una observación que se puede hacer es que si existen dos números a y b tales que su producto es divisible por su suma entonces no son primos relativos, es decir, su MCD no es uno. Esto se puede demostrar utilizando el algoritmo de Euclides .
Por lo tanto, al usar la observación anterior, se pueden seguir los siguientes pasos para calcular el resultado: 
 

1. Si a puede expresarse como k * x y b puede expresarse como k * y tal que x e y son coprimos , entonces: 
 

a + b = k(x + y)
a * b = k2

2. Ahora, al dividir los valores anteriores: 
 

(a * b) /(a + b) = k * ((x * y)/(x + y)). 

3. Como se sabe que xey son coprimos, ( x * y ) no será divisible por ( x + y ). Esto significa que k debe ser divisible por x + y.

4. Por lo tanto, k es el mayor factor posible para el cual ( k * x ) y ( k * y ) siguen siendo menores que N .

5. Claramente, el valor mínimo de k para el cual es divisible por (x + y) es ( x + y ). Esto significa que (x + y) * y ≤ N y (x + y) * x ≤ NORTE.

6. Por lo tanto, todos los factores se verifican desde 1 hasta N ^0.5 .

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

// C++ implementation to  find the largest value
// of a + b satisfying the given condition
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum sum of
// a + b satisfying the given condition
int getLargestSum(int N)
{
    int max_sum = 0; // Initialize max_sum
 
    // Consider all possible pairs and check
    // the sum divides product property
    for (int i = 1; i * i <= N; i++) {
        for (int j = i + 1; j * j <= N; j++) {
 
            // To find the largest factor k
            int k = N / j;
            int a = k * i;
            int b = k * j;
 
            // Check if the product is
            // divisible by the sum
            if (a <= N && b <= N
                && a * b % (a + b) == 0)
 
                // Storing the maximum sum
                // in the max_sum variable
                max_sum = max(max_sum, a + b);
        }
    }
 
    // Return the max_sum value
    return max_sum;
}
 
// Driver code
int main()
{
    int N = 25;
    int max_sum = getLargestSum(N);
 
    cout << max_sum << endl;
    return 0;
}

// Java implementation to find the largest value
// of a + b satisfying the given condition
 
class GFG{
 
// Function to return the maximum sum of
// a + b satisfying the given condition
static int getLargestSum(int N)
{
    // Initialize max_sum
    int max_sum = 0;
 
    // Consider all possible pairs and check
    // the sum divides product property
    for (int i = 1; i * i <= N; i++) {
         for (int j = i + 1; j * j <= N; j++) {
 
              // To find the largest factor k
              int k = N / j;
              int a = k * i;
              int b = k * j;
 
               // Check if the product is
               // divisible by the sum
               if (a <= N && b <= N &&
                   a * b % (a + b) == 0)
 
                   // Storing the maximum sum
                   // in the max_sum variable
                   max_sum = Math.max(max_sum, a + b);
        }
    }
 
    // Return the max_sum value
    return max_sum;
}
 
// Driver code
public static void main(String[] args)
{
    int N = 25;
    int max_sum = getLargestSum(N);
    System.out.print(max_sum + "\n");
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation to find the largest value
# of a + b satisfying the given condition
 
# Function to return the maximum sum of
# a + b satisfying the given condition
def getLargestSum(N) :
 
    max_sum = 0; # Initialize max_sum
 
    # Consider all possible pairs and check
    # the sum divides product property
    for i in range(1, int(N ** (1/2))+1) :
        for j in range(i + 1, int(N ** (1/2)) + 1) :
             
            # To find the largest factor k
            k = N // j;
            a = k * i;
            b = k * j;
             
            # Check if the product is
            # divisible by the sum
            if (a <= N and b <= N and a * b % (a + b) == 0) :
                # Storing the maximum sum
                # in the max_sum variable
                max_sum = max(max_sum, a + b);
                 
    # Return the max_sum value
    return max_sum;
     
# Driver code
if __name__ == "__main__" :
    N = 25;
    max_sum = getLargestSum(N);
    print(max_sum);
 
# This code is contributed by AnkitRai01

// C# implementation to find the largest value
// of a + b satisfying the given condition
using System;
 
class GFG{
 
// Function to return the maximum sum of
// a + b satisfying the given condition
static int getLargestSum(int N)
{
     
    // Initialize max_sum
    int max_sum = 0;
 
    // Consider all possible pairs and check
    // the sum divides product property
    for(int i = 1; i * i <= N; i++)
    {
       for(int j = i + 1; j * j <= N; j++)
       {
          // To find the largest factor k
          int k = N / j;
          int a = k * i;
          int b = k * j;
           
          // Check if the product is
          // divisible by the sum
          if (a <= N && b <= N &&
              a * b % (a + b) == 0)
               
              // Storing the maximum sum
              // in the max_sum variable
              max_sum = Math.Max(max_sum, a + b);
        }
    }
 
    // Return the max_sum value
    return max_sum;
}
 
// Driver code
static public void Main(String[] args)
{
    int N = 25;
    int max_sum = getLargestSum(N);
     
    Console.Write(max_sum + "\n");
}
}
 
// This code is contributed by gauravrajput1

<script>
    // Javascript implementation to find the largest value
    // of a + b satisfying the given condition
     
    // Function to return the maximum sum of
    // a + b satisfying the given condition
    function getLargestSum(N)
    {
 
        // Initialize max_sum
        let max_sum = 0;
 
        // Consider all possible pairs and check
        // the sum divides product property
        for(let i = 1; i * i <= N; i++)
        {
           for(let j = i + 1; j * j <= N; j++)
           {
              // To find the largest factor k
              let k = parseInt(N / j, 10);
              let a = k * i;
              let b = k * j;
 
              // Check if the product is
              // divisible by the sum
              if (a <= N && b <= N &&
                  a * b % (a + b) == 0)
 
                  // Storing the maximum sum
                  // in the max_sum variable
                  max_sum = Math.max(max_sum, a + b);
            }
        }
 
        // Return the max_sum value
        return max_sum;
    }
     
    let N = 25;
    let max_sum = getLargestSum(N);
      
    document.write(max_sum + "</br>");
 
// This code is contributed by divyesh072019.
</script>

36

Complejidad del tiempo: aunque hay dos bucles, cada bucle se ejecuta como máximo en sqrt(N) de tiempo. Por lo tanto, la complejidad temporal total O(N) .

Espacio Auxiliar: O(1)