Minimice los pasos para llegar a K desde 0 agregando 1 o duplicando en cada paso

Dado un entero positivo K , la tarea es encontrar el número mínimo de operaciones de los siguientes dos tipos, requeridas para cambiar 0 a K: 
 

• Añadir uno al operando
• Multiplica el operando por 2.

Ejemplos: 
 

Entrada: K = 1 
Salida: 1 
Explicación: 
Paso 1: 0 + 1 = 1 = K
Entrada: K = 4 
Salida: 3 
Explicación: 
Paso 1: 0 + 1 = 1, 
Paso 2: 1 * 2 = 2, 
Paso 3 : 2 * 2 = 4 = K 
 

Acercarse: 
 

• Si K es un número impar, el último paso debe ser sumarle 1.
• Si K es un número par, el último paso es multiplicar por 2 para minimizar el número de pasos.
• Cree una tabla dp[] que almacene en cada dp[i] , los pasos mínimos necesarios para llegar a i . 
   

Prueba:

• Consideremos un número par X
• Ahora tenemos dos opciones:
  i) X-1
  ii)X/2
• Ahora, si elegimos X-1 :
  -> X-1 es un número impar, ya que X es par
  -> Por lo tanto, elegimos restar 1  operación y tenemos X-2
  -> Ahora tenemos X-2, que también es par número, ahora nuevamente tenemos dos opciones para restar 1 o dividir por 2
  -> Ahora elijamos dividir por 2 operación, por lo tanto tenemos (X – 2)/2 => (X/2) -1
• Ahora si elegimos X/2 :
  -> Podemos hacer la operación restar 1 para llegar a (X/2)-1
• Ahora consideremos la secuencia de ambos casos:
  Cuando elegimos X-1: X -> X-1 -> X-2 -> (X/2)-1 [totalmente tres operaciones]
  Cuando elegimos X/2: X -> X/2 -> (X/2)-1 [totalmente dos operaciones]
   

Este diagrama muestra cómo la elección de la operación de división para números pares conduce a la solución óptima recursivamente

• Por lo tanto, podemos decir que para un número par dado, elegir la operación de dividir por 2 siempre nos dará el número mínimo de pasos
• Por lo tanto probado

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

// C++ program to implement the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum operations
int minOperation(int k)
{
    // vector dp is initialised
    // to store the steps
    vector<int> dp(k + 1, 0);
 
    for (int i = 1; i <= k; i++) {
 
        dp[i] = dp[i - 1] + 1;
 
        // For all even numbers
        if (i % 2 == 0) {
            dp[i]
                = min(dp[i],
                      dp[i / 2] + 1);
        }
    }
    return dp[k];
}
 
// Driver Code
int main()
{
    int K = 12;
    cout << minOperation(k);
}

// Java program to implement the above approach
class GFG{
     
// Function to find minimum operations
static int minOperation(int k)
{
     
    // dp is initialised
    // to store the steps
    int dp[] = new int[k + 1];
 
    for(int i = 1; i <= k; i++)
    {
       dp[i] = dp[i - 1] + 1;
        
       // For all even numbers
       if (i % 2 == 0)
       {
           dp[i] = Math.min(dp[i], dp[i / 2] + 1);
       }
    }
    return dp[k];
}
 
// Driver Code
public static void main (String []args)
{
    int K = 12;
    System.out.print( minOperation(K));
}
}
 
// This code is contributed by chitranayal

# Python3 program to implement the above approach
 
# Function to find minimum operations
def minOperation(k):
     
    # dp is initialised
    # to store the steps
    dp = [0] * (k + 1)
 
    for i in range(1, k + 1):
        dp[i] = dp[i - 1] + 1
 
        # For all even numbers
        if (i % 2 == 0):
            dp[i]= min(dp[i], dp[i // 2] + 1)
 
    return dp[k]
 
# Driver Code
if __name__ == '__main__':
     
    k = 12
     
    print(minOperation(k))
 
# This code is contributed by mohit kumar 29

// C# program to implement the above approach
using System;
class GFG{
     
// Function to find minimum operations
static int minOperation(int k)
{
     
    // dp is initialised
    // to store the steps
    int []dp = new int[k + 1];
 
    for(int i = 1; i <= k; i++)
    {
        dp[i] = dp[i - 1] + 1;
             
        // For all even numbers
        if (i % 2 == 0)
        {
            dp[i] = Math.Min(dp[i], dp[i / 2] + 1);
        }
    }
    return dp[k];
}
 
// Driver Code
public static void Main()
{
    int K = 12;
    Console.Write(minOperation(K));
}
}
 
// This code is contributed by Nidhi_Biet

<script>
// Javascript implementation of the above approach
 
// Function to find minimum operations
function minOperation(k)
{
       
    // dp is initialised
    // to store the steps
    let dp = Array.from({length: k+1}, (_, i) => 0);
   
    for(let i = 1; i <= k; i++)
    {
       dp[i] = dp[i - 1] + 1;
          
       // For all even numbers
       if (i % 2 == 0)
       {
           dp[i] = Math.min(dp[i], dp[i / 2] + 1);
       }
    }
    return dp[k];
}
 
  // Driver Code   
    let K = 12;
    document.write( minOperation(K));
  
 // This code is contributed by target_2.
</script>

5

Complejidad temporal: O(k)
Espacio auxiliar: O(k)