Número mínimo de movimientos para llegar a N a partir de (1, 1)

Dado un entero N y una tabla infinita donde la i ^-ésima fila y la j ^-ésima columna contienen el valor i *j . La tarea es encontrar el número mínimo de movimientos para llegar a la celda que contiene N a partir de la celda (1, 1) . 
Nota: De (i, j) solo los movimientos válidos son (i + 1, j) y (i, j + 1)  
Ejemplos: 
 

Entrada: N = 10 
Salida: 5 
(1, 1) -> (2, 1) -> (2, 2) -> (2, 3) -> (2, 4) -> (2, 5)
Entrada: N = 7 
Salida: 6 
 

Enfoque: Tenga en cuenta que se puede llegar a cualquier celda (i, j) en i + j – 2 pasos. Por lo tanto, solo se requiere el par (i, j) con i * j = N que minimiza i + j . Se puede averiguar encontrando todos los pares posibles (i, j) y verificándolos en O(√N) . Para ello, sin pérdida de generalidad, se puede suponer que i ≤ j y i ≤ √N ya que N = i * j ≥ i ² . Entonces √N ≥ yo ² es decir √N ≥ yo . 
Por lo tanto, iterar sobre todos los valores posibles de i de 1 a√N y, entre todos los pares posibles (i, j) , elige el valor más bajo de i + j – 2 y esa es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum number
// of moves required to reach the cell
// containing N starting from (1, 1)
int min_moves(int n)
{
    // To store the required answer
    int ans = INT_MAX;
 
    // For all possible values of divisors
    for (int i = 1; i * i <= n; i++) {
 
        // If i is a divisor of n
        if (n % i == 0) {
 
            // Get the moves to reach n
            ans = min(ans, i + n / i - 2);
        }
    }
 
    // Return the required answer
    return ans;
}
 
// Driver code
int main()
{
    int n = 10;
 
    cout << min_moves(n);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
     
// Function to return the minimum number
// of moves required to reach the cell
// containing N starting from (1, 1)
static int min_moves(int n)
{
    // To store the required answer
    int ans = Integer.MAX_VALUE;
 
    // For all possible values of divisors
    for (int i = 1; i * i <= n; i++)
    {
 
        // If i is a divisor of n
        if (n % i == 0)
        {
 
            // Get the moves to reach n
            ans = Math.min(ans, i + n / i - 2);
        }
    }
 
    // Return the required answer
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 10;
 
    System.out.println(min_moves(n));
}
}
 
// This code is contributed by Code_Mech

# Python3 implementation of the approach
import sys
 
from math import sqrt
 
# Function to return the minimum number
# of moves required to reach the cell
# containing N starting from (1, 1)
def min_moves(n) :
 
    # To store the required answer
    ans = sys.maxsize;
 
    # For all possible values of divisors
    for i in range(1, int(sqrt(n)) + 1) :
 
        # If i is a divisor of n
        if (n % i == 0) :
 
            # Get the moves to reach n
            ans = min(ans, i + n // i - 2);
 
    # Return the required answer
    return ans;
 
# Driver code
if __name__ == "__main__" :
 
    n = 10;
 
    print(min_moves(n));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
     
class GFG
{
     
// Function to return the minimum number
// of moves required to reach the cell
// containing N starting from (1, 1)
static int min_moves(int n)
{
    // To store the required answer
    int ans = int.MaxValue;
 
    // For all possible values of divisors
    for (int i = 1; i * i <= n; i++)
    {
 
        // If i is a divisor of n
        if (n % i == 0)
        {
 
            // Get the moves to reach n
            ans = Math.Min(ans, i + n / i - 2);
        }
    }
 
    // Return the required answer
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    int n = 10;
 
    Console.WriteLine(min_moves(n));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
    // JavaScript implementation of the approach
     
    // Function to return the minimum number
    // of moves required to reach the cell
    // containing N starting from (1, 1)
    function min_moves(n)
    {
        // To store the required answer
        let ans = Number.MAX_VALUE;
 
        // For all possible values of divisors
        for (let i = 1; i * i <= n; i++)
        {
 
            // If i is a divisor of n
            if (n % i == 0)
            {
 
                // Get the moves to reach n
                ans = Math.min(ans, i + parseInt(n / i, 10) - 2);
            }
        }
 
        // Return the required answer
        return ans;
    }
     
    let n = 10;
   
    document.write(min_moves(n));
             
</script>

5

Complejidad de tiempo: O(sqrt(n))

Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.