Maximice los pasos para reducir N a 0 restando cualquier valor excepto 1 y N en cada paso

Dado un número N , la tarea es encontrar el número máximo de pasos para convertir N a cero, donde en cada paso se resta un número m ( 1 < m < N (valor inicial de N)) de N. Si es imposible convertir N a 0 de esta manera, imprima -1 .

Nota: Los valores de m pueden ser diferentes en diferentes pasos.

Ejemplos: 

Entrada: N = 14
Salida: 7
Explicación: Los pasos son los siguientes:
14 – 2 = 12 – 1ra Operación
12 – 2 = 10 – 2da Operación
10 – 2 = 8 – 3ra Operación
8 – 2 = 6 – 4ta Operación
6 – 2 = 4 – 5ª operación
4 -2 = 2 – 6ª operación
2-2 = 0 – 7ª operación

Entrada: N = 2
Salida: -1
Explicación: No es posible obtener 0

Entrada: N = 5
Salida: 2
Explicación: Resta 2 y 3 de 5 respectivamente

Enfoque: El problema se puede resolver con base en la simple observación. Si N = 1, 2 o 3, no hay forma posible de obtener 0 de N. En todos los demás casos hay una forma posible. El número de pasos será máximo cuando se reste el valor mínimo en cada paso, es decir, 2 . Entonces, el número total de pasos se convierte en N/2 . (Cuando N es impar, el último valor restado será 3 porque 1 no está permitido)

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

// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find
// the minimum number of steps
int minSteps(int N)
{
    if (N == 1 || N == 2 || N == 3)
        return -1;
    return (N / 2);
}
 
// Driver code
int main()
{
    int N;
    N = 5;
    cout << minSteps(N);
    return 0;
}

// Java code to implement above approach
class GFG
{
 
  // Function to find
  // the minimum number of steps
  static int minSteps(int N)
  {
    if (N == 1 || N == 2 || N == 3)
      return -1;
    return (N / 2);
  }
 
  // Driver Code:
  public static void main(String args[])
  {
    int N;
    N = 5;
    System.out.println(minSteps(N));
  }
}
 
// This code is contributed by gfgking

# Python code to implement above approach
 
# Function to find
# the minimum number of steps
def minSteps (N):
    if (N == 1 or N == 2 or N == 3):
        return -1;
    return N // 2;
 
# Driver code
N = 5;
print(minSteps(N));
 
# This code is contributed by gfgking

// C# code to implement above approach
using System;
class GFG
{
 
// Function to find
// the minimum number of steps
static int minSteps(int N)
{
    if (N == 1 || N == 2 || N == 3)
        return -1;
    return (N / 2);
}
 
// Driver Code:
public static void Main()
{
    int N;
    N = 5;
    Console.WriteLine(minSteps(N));
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript code to implement above approach
 
    // Function to find
    // the minimum number of steps
    const minSteps = (N) => {
        if (N == 1 || N == 2 || N == 3)
            return -1;
        return parseInt(N / 2);
    }
 
    // Driver code
 
    let N;
    N = 5;
    document.write(minSteps(N));
 
// This code is contributed by rakeshsahni
 
</script>

2

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)