Dado un entero N , la tarea es encontrar dos enteros con la mínima suma posible tal que su producto sea estrictamente mayor que N .
Ejemplos:
Entrada: N = 10
Salida: 7
Explicación: Los enteros son 3 y 4. Su producto es 3 × 4 = 12, que es mayor que N.Entrada: N = 1
Salida: 3
Explicación: Los enteros son 1 y 2. Su producto es 1 × 2 = 2, que es mayor que N.
Enfoque ingenuo: Deje que los números requeridos sean A y B. La idea se basa en la observación de que para minimizar su suma A debe ser el número más pequeño mayor que √N . Una vez que se encuentra A , B será igual al número más pequeño para el cual A×B > N , que se puede encontrar linealmente .
Complejidad de Tiempo: O(√N)
Espacio Auxiliar: O(1)
Enfoque eficiente: la solución anterior se puede optimizar utilizando la búsqueda binaria para encontrar A y B. Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables bajo = 0 y alto = 10 9 .
- Iterar hasta que (alto – bajo) sea mayor que 1 y hacer lo siguiente:
- Encuentre el valor de rango medio medio como (bajo + alto)/2 .
- Ahora, compare √N con el elemento medio mid , y si √N es menor o igual que el elemento medio, entonces alto como mid .
- De lo contrario, actualice bajo como medio .
- Después de todos los pasos anteriores, configure A = alto .
- Repita el mismo procedimiento para encontrar B tal que A×B > N.
- Después de los pasos anteriores, imprima la suma de A y B como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
// Function to find the minimum sum of
// two integers such that their product
// is strictly greater than N
void minSum(int N)
{
// Initialise low as 0 and
// high as 1e9
ll low = 0, high = 1e9;
// Iterate to find the first number
while (low + 1 < high) {
// Find the middle value
ll mid = low + (high - low) / 2;
// If mid^2 is greater than
// equal to A, then update
// high to mid
if (mid * mid >= N) {
high = mid;
}
// Otherwise update low
else {
low = mid;
}
}
// Store the first number
ll first = high;
// Again, set low as 0 and
// high as 1e9
low = 0;
high = 1e9;
// Iterate to find the second number
while (low + 1 < high) {
// Find the middle value
ll mid = low + (high - low) / 2;
// If first number * mid is
// greater than N then update
// high to mid
if (first * mid > N) {
high = mid;
}
// Else, update low to mid
else {
low = mid;
}
}
// Store the second number
ll second = high;
// Print the result
cout << first + second;
}
// Driver Code
int main()
{
int N = 10;
// Function Call
minSum(N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to find the minimum sum of
// two integers such that their product
// is strictly greater than N
static void minSum(int N)
{
// Initialise low as 0 and
// high as 1e9
long low = 0, high = 1000000000;
// Iterate to find the first number
while (low + 1 < high)
{
// Find the middle value
long mid = low + (high - low) / 2;
// If mid^2 is greater than
// equal to A, then update
// high to mid
if (mid * mid >= N)
{
high = mid;
}
// Otherwise update low
else
{
low = mid;
}
}
// Store the first number
long first = high;
// Again, set low as 0 and
// high as 1e9
low = 0;
high = 1000000000;
// Iterate to find the second number
while (low + 1 < high)
{
// Find the middle value
long mid = low + (high - low) / 2;
// If first number * mid is
// greater than N then update
// high to mid
if (first * mid > N)
{
high = mid;
}
// Else, update low to mid
else
{
low = mid;
}
}
// Store the second number
long second = high;
// Print the result
System.out.println(first + second);
}
// Driver Code
public static void main(String[] args)
{
int N = 10;
// Function Call
minSum(N);
}
}
// This code is contributed by Dharanendra L V
Python3
# Python3 program for the above approach # Function to find the minimum sum of # two integers such that their product # is strictly greater than N def minSum(N): # Initialise low as 0 and # high as 1e9 low = 0 high = 1000000000 # Iterate to find the first number while (low + 1 < high): # Find the middle value mid = low + (high - low) / 2 # If mid^2 is greater than # equal to A, then update # high to mid if (mid * mid >= N): high = mid # Otherwise update low else: low = mid # Store the first number first = high # Again, set low as 0 and # high as 1e9 low = 0 high = 1000000000 # Iterate to find the second number while (low + 1 < high): # Find the middle value mid = low + (high - low) / 2 # If first number * mid is # greater than N then update # high to mid if (first * mid > N): high = mid # Else, update low to mid else: low = mid # Store the second number second = high # Print the result print(round(first + second)) # Driver Code N = 10 # Function Call minSum(N) # This code is contributed by Dharanendra L V
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum sum of
// two integers such that their product
// is strictly greater than N
static void minSum(int N)
{
// Initialise low as 0 and
// high as 1e9
long low = 0, high = 1000000000;
// Iterate to find the first number
while (low + 1 < high)
{
// Find the middle value
long mid = low + (high - low) / 2;
// If mid^2 is greater than
// equal to A, then update
// high to mid
if (mid * mid >= N)
{
high = mid;
}
// Otherwise update low
else
{
low = mid;
}
}
// Store the first number
long first = high;
// Again, set low as 0 and
// high as 1e9
low = 0;
high = 1000000000;
// Iterate to find the second number
while (low + 1 < high)
{
// Find the middle value
long mid = low + (high - low) / 2;
// If first number * mid is
// greater than N then update
// high to mid
if (first * mid > N)
{
high = mid;
}
// Else, update low to mid
else
{
low = mid;
}
}
// Store the second number
long second = high;
// Print the result
Console.WriteLine( first + second);
}
// Driver Code
static public void Main()
{
int N = 10;
// Function Call
minSum(N);
}
}
// This code is contributed by Dharanendra L V
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum sum of
// two integers such that their product
// is strictly greater than N
function minSum(N)
{
// Initialise low as 0 and
// high as 1e9
let low = 0, high = 1000000000;
// Iterate to find the first number
while (low + 1 < high) {
// Find the middle value
let mid = low + parseInt((high - low) / 2);
// If mid^2 is greater than
// equal to A, then update
// high to mid
if (mid * mid >= N) {
high = mid;
}
// Otherwise update low
else {
low = mid;
}
}
// Store the first number
let first = high;
// Again, set low as 0 and
// high as 1e9
low = 0;
high = 1000000000;
// Iterate to find the second number
while (low + 1 < high) {
// Find the middle value
let mid = low + parseInt((high - low) / 2);
// If first number * mid is
// greater than N then update
// high to mid
if (first * mid > N) {
high = mid;
}
// Else, update low to mid
else {
low = mid;
}
}
// Store the second number
let second = high;
// Print the result
document.write(first + second);
}
// Driver Code
let N = 10;
// Function Call
minSum(N);
// This code is contributed by rishavmahato348.
</script>
Producción:
7
Complejidad temporal: O(log N)
Espacio auxiliar: O(1)
Enfoque más eficiente: para optimizar el enfoque anterior, la idea se basa en la desigualdad de la progresión aritmética y geométrica , como se ilustra a continuación.
De la desigualdad, Si hay dos enteros A y B,
(A + B)/2 ≥ √(A×B)
Ahora, A×B = Producto de los dos enteros, que es N y A+B es suma (= S) .
Por lo tanto, S ≥ 2*√N
Para obtener un producto estrictamente mayor que N, la ecuación anterior se transforma en: S ≥ 2*√(N+1)
A continuación se muestra el programa para el enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum sum of
// two integers such that their product
// is strictly greater than N
void minSum(int N)
{
// Store the answer using the
// AP-GP inequality
int ans = ceil(2 * sqrt(N + 1));
// Print the answer
cout << ans;
}
// Driver Code
int main()
{
int N = 10;
// Function Call
minSum(N);
return 0;
}
Java
// Java program for the above approach
import java.lang.*;
class GFG{
// Function to find the minimum sum of
// two integers such that their product
// is strictly greater than N
static void minSum(int N)
{
// Store the answer using the
// AP-GP inequality
int ans = (int)Math.ceil(2 * Math.sqrt(N + 1));
// Print the answer
System.out.println( ans);
}
// Driver Code
public static void main(String[] args)
{
int N = 10;
// Function Call
minSum(N);
}
}
// This code is contributed by Dharanendra L V
Python3
# Python3 program for the above approach import math # Function to find the minimum sum of # two integers such that their product # is strictly greater than N def minSum(N): # Store the answer using the # AP-GP inequality ans = math.ceil(2 * math.sqrt(N + 1)) # Print the result print(math.trunc(ans)) # Driver Code N = 10 # Function Call minSum(N) # This code is contributed by Dharanendra L V
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum sum of
// two integers such that their product
// is strictly greater than N
static void minSum(int N)
{
// Store the answer using the
// AP-GP inequality
int ans = (int)Math.Ceiling(2 * Math.Sqrt(N + 1));
// Print the answer
Console.WriteLine( ans);
}
// Driver Code
static public void Main()
{
int N = 10;
// Function Call
minSum(N);
}
}
// This code is contributed by Dharanendra L V
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum sum of
// two integers such that their product
// is strictly greater than N
function minSum(N)
{
// Store the answer using the
// AP-GP inequality
let ans = Math.ceil(2 * Math.sqrt(N + 1));
// Print the answer
document.write(ans);
}
// Driver Code
let N = 10;
// Function Call
minSum(N);
</script>
Producción:
7
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por koulick_sadhu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA