Alcance N desde 1 incrementando en 1 o duplicando el valor como máximo D veces

Dado un número entero N y un número entero D , la tarea es llegar a N desde 1 en movimientos mínimos ya sea sumando 1 o duplicando el valor, pero la duplicación se puede realizar como máximo D veces.

Ejemplos:

Entrada: N = 20, D = 4
Salida: 5
Explicación: El flujo se puede ver como 1 -> 2 -> 4 -> 5 -> 10 -> 20

Entrada: N = 10, D = 0
Salida: 9

Enfoque: La tarea se puede resolver usando recursividad:

• Declarar una variable para almacenar los movimientos mínimos como respuesta
• Primero verifique si se alcanza el objetivo , si es así, busque almacenar el mínimo de movimientos actuales y responda en ans
• Luego verifique si los movimientos de duplicación D se han agotado , pero aún no se ha alcanzado el objetivo,
  • Luego agregue los movimientos restantes como movimientos incrementales agregando ( N-current_value ) en current_moves.
  • Encuentre el mínimo de current_moves y ans , y guárdelo en ans
• Si el valor_actual ha cruzado N , devuelve
• Si ninguno de los casos anteriores coincide, llame recursivamente a la función para hacer las dos cosas a continuación una por una:
  • duplicar el valor_actual
  • agregue 1 a current_value.
• Devuelve la respuesta final .

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

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
int ans = 0;
 
// Utility function to find
// the minimum number of moves required
void move(int& N, int& D, long s,
          int cd, int temp)
{
 
    if (s == N) {
        ans = min(ans, temp);
        return;
    }
    if (cd == D && s <= N) {
        temp += (N - s);
        ans = min(ans, temp);
        return;
    }
    if (s > N)
        return;
    move(N, D, s * 2, cd + 1, temp + 1);
    move(N, D, s + 1, cd, temp + 1);
}
 
// Function to call the utility function
int minMoves(int N, int D)
{
    ans = N;
    move(N, D, 1, 0, 0);
    return ans;
}
 
// Driver code
int main()
{
    int N = 20, D = 4;
 
    cout << minMoves(N, D);
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  static int ans = 0;
 
  // Utility function to find
  // the minimum number of moves required
  static void move(int N, int D, long s,  int cd, int temp)
  {
 
    if (s == N) {
      ans = Math.min(ans, temp);
      return;
    }
    if (cd == D && s <= N) {
      temp += (N - s);
      ans = Math.min(ans, temp);
      return;
    }
    if (s > N)
      return;
    move(N, D, s * 2, cd + 1, temp + 1);
    move(N, D, s + 1, cd, temp + 1);
  }
 
  // Function to call the utility function
  static int minMoves(int N, int D)
  {
    ans = N;
    move(N, D, 1, 0, 0);
    return ans;
  }
 
  // Driver code
  public static void main (String[] args) {
    int N = 20, D = 4;
 
    System.out.print(minMoves(N, D));
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python program for the above approach
ans = 0;
 
# Utility function to find
# the minimum number of moves required
def move(N, D, s, cd, temp):
    global ans;
    if (s == N):
        ans = min(ans, temp);
        return;
 
    if (cd == D and s <= N):
        temp += (N - s);
        ans = min(ans, temp);
        return;
 
    if (s > N):
        return;
    move(N, D, s * 2, cd + 1, temp + 1);
    move(N, D, s + 1, cd, temp + 1);
 
# Function to call the utility function
def minMoves(N, D):
    global ans;
    ans = N;
    move(N, D, 1, 0, 0);
    return ans;
 
# Driver code
if __name__ == '__main__':
    N = 20;
    D = 4;
 
    print(minMoves(N, D));
 
# This code is contributed by 29AjayKumar

// C# program for the above approach
using System;
class GFG {
 
  static int ans = 0;
 
  // Utility function to find
  // the minimum number of moves required
  static void move(int N, int D, long s,  int cd, int temp)
  {
 
    if (s == N) {
      ans = Math.Min(ans, temp);
      return;
    }
    if (cd == D && s <= N) {
      temp += (int)(N - s);
      ans = Math.Min(ans, temp);
      return;
    }
    if (s > N)
      return;
    move(N, D, s * 2, cd + 1, temp + 1);
    move(N, D, s + 1, cd, temp + 1);
  }
 
  // Function to call the utility function
  static int minMoves(int N, int D)
  {
    ans = N;
    move(N, D, 1, 0, 0);
    return ans;
  }
 
  // Driver code
  public static void Main () {
    int N = 20, D = 4;
 
    Console.Write(minMoves(N, D));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript code for the above approach
    let ans = 0;
 
    // Utility function to find
    // the minimum number of moves required
    function move(N, D, s,
        cd, temp) {
 
        if (s == N) {
            ans = Math.min(ans, temp);
            return;
        }
        if (cd == D && s <= N) {
            temp += (N - s);
            ans = Math.min(ans, temp);
            return;
        }
        if (s > N)
            return;
        move(N, D, s * 2, cd + 1, temp + 1);
        move(N, D, s + 1, cd, temp + 1);
    }
 
    // Function to call the utility function
    function minMoves(N, D) {
        ans = N;
        move(N, D, 1, 0, 0);
        return ans;
    }
 
    // Driver code
    let N = 20, D = 4;
    document.write(minMoves(N, D));
 
     // This code is contributed by Potta Lokesh
</script>

5

Complejidad temporal: O(N)
Espacio auxiliar: O(1)