Pasos mínimos para reducir N a 0 mediante operaciones dadas

Dé un número entero N , la tarea es encontrar el número mínimo de movimientos para reducir N a 0 mediante una de las siguientes operaciones:

  • Reducir N en 1.
  • Reducir N a (N/2), si N es divisible por 2.
  • Reducir N a (N/3), si N es divisible por 3.

Ejemplos:

Entrada: N = 10
Salida: 4
Explicación: 
Aquí N = 10
Paso 1: Reduciendo N por 1, es decir, 10 – 1 = 9.  
Paso 2: Dado que 9 es divisible por 3, redúzcalo a N/3 = 9/3 = 3
Paso 3: Dado que nuevamente 3 es divisible por 3, repita nuevamente el paso 2, es decir, 3/3 = 1.
Paso 4: 1 puede reducirse por el paso 1, es decir, 1-1 = 0  
Por lo tanto, se necesitan 4 pasos para reducir N a 0.

Entrada: N = 6
Salida: 3
Explicación: 
Aquí N = 6
Paso 1: Como 6 es divisible por 2, entonces 6/2 =3
Paso 2: Como 3 es divisible por 3, entonces 3/3 = 1. 
Paso 3: Reduzca N a N-1 en 1, 1-1 = 0.
Por lo tanto, se necesitan 3 pasos para reducir N a 0.

Enfoque ingenuo: la idea es utilizar la recursividad para todos los movimientos posibles. A continuación se muestran los pasos:

  1. Observe ese caso base para el problema, si N < 2 entonces para todos los casos la respuesta será N misma.
  2. En cada valor de N , elija entre 2 casos posibles:
    • Reduzca n hasta n % 2 == 0 y luego actualice n /= 2 con count = 1 + n%2 + f(n/2)
    • Reducir n hasta n % 3 == 0 y luego actualizar n /= 3 con cuenta = 1 + n%3 + f(n/3)
  3. Tanto el cálculo da como resultado la relación de recurrencia como:

 count = 1 + min(n%2 + f(n/2), n%3 + f(n/3))
donde, f(n) es el mínimo de movimientos para reducir N a 0.

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum
// number to steps to reduce N to 0
int minDays(int n)
{
     
    // Base case
    if (n < 1)
        return n;
         
    // Recursive call to count the
    // minimum steps needed
    int cnt = 1 + min(n % 2 + minDays(n / 2),
                      n % 3 + minDays(n / 3));
 
    // Return the answer
    return cnt;
}
 
// Driver Code
int main()
{
     
    // Given number N
    int N = 6;
     
    // Function call
    cout << minDays(N);
     
    return 0;
}
 
// This code is contributed by 29AjayKumar

Java

// Java program for the above approach
class GFG{
   
    // Function to find the minimum
    // number to steps to reduce N to 0
    static int minDays(int n)
    {
 
        // Base case
        if (n < 1)
            return n;
 
        // Recursive Call to count the
        // minimum steps needed
        int cnt = 1 + Math.min(n % 2 + minDays(n / 2),
                               n % 3 + minDays(n / 3));
 
        // Return the answer
        return cnt;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given Number N
        int N = 6;
 
        // Function Call
        System.out.print(minDays(N));
    }
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 program for the above approach
 
# Function to find the minimum
# number to steps to reduce N to 0
def minDays(n):
 
    # Base case
    if n < 1:
        return n
       
    # Recursive Call to count the
    # minimum steps needed
    cnt = 1 + min(n % 2 + minDays(n // 2),
                  n % 3 + minDays(n // 3))
 
    # Return the answer
    return cnt
 
# Driver Code
 
# Given Number N
N = 6
 
# Function Call
print(str(minDays(N)))

C#

// C# program for the above approach
using System;
class GFG{
 
// Function to find the minimum
// number to steps to reduce N to 0
static int minDays(int n)
{   
    // Base case
    if (n < 1)
        return n;
 
    // Recursive call to count the
    // minimum steps needed
    int cnt = 1 + Math.Min(n % 2 + minDays(n / 2),
                           n % 3 + minDays(n / 3));
 
    // Return the answer
    return cnt;
}
 
// Driver Code
public static void Main(String[] args)
{   
    // Given number N
    int N = 6;
 
    // Function call
    Console.Write(minDays(N));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to find the minimum
// number to steps to reduce N to 0
function minDays(n)
{
     
    // Base case
    if (n < 1)
        return n;
         
    // Recursive call to count the
    // minimum steps needed
    var cnt = 1 + Math.min(n % 2 + minDays(parseInt(n / 2)),
                      n % 3 + minDays(parseInt(n / 3)));
 
    // Return the answer
    return cnt;
}
 
// Driver Code
// Given number N
var N = 6;
 
// Function call
document.write( minDays(N));
 
 
</script>
Producción: 

4

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

Enfoque Eficiente: La idea es usar Programación Dinámica . El enfoque recursivo anterior da como resultado TLE debido a la cantidad de subproblemas repetidos. Para optimizar el método anterior utilizando un diccionario para realizar un seguimiento de los valores cuya llamada recursiva ya se realizó para reducir el cálculo adicional de modo que se pueda acceder al valor más rápido.

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

C++

// C++ program for
// the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to find the minimum
// number to steps to reduce N to 0
int count(int n)
{
  // Dictionary for storing
  // the precomputed sum
  map<int, int> dp;
 
  // Bases Cases
  dp[0] = 0;
  dp[1] = 1;
 
  // Check if n is not in dp then
  // only call the function so as
  // to reduce no of recursive calls
  if ((dp.find(n) == dp.end()))
    dp[n] = 1 + min(n % 2 +
                    count(n / 2), n % 3 +
                    count(n / 3));
 
  // Return the answer
  return dp[n];
}
 
// Driver Code
int main()
{   
  // Given number N
  int N = 6;
 
  // Function call
  cout << count(N);
}
 
// This code is contributed by gauravrajput1

Java

// Java program for the above approach
import java.util.HashMap;
 
class GFG{
     
// Function to find the minimum
// number to steps to reduce N to 0
static int count(int n)
{
     
    // Dictionary for storing
    // the precomputed sum
    HashMap<Integer,
            Integer> dp = new HashMap<Integer,
                                      Integer>();
 
    // Bases Cases
    dp.put(0, 0);
    dp.put(1, 1);
 
    // Check if n is not in dp then
    // only call the function so as
    // to reduce no of recursive calls
    if (!dp.containsKey(n))
        dp.put(n, 1 + Math.min(n % 2 +
                 count(n / 2), n % 3 +
                 count(n / 3)));
 
    // Return the answer
    return dp.get(n);
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given number N
    int N = 6;
 
    // Function call
    System.out.println(String.valueOf((count(N))));
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program for the above approach
 
# Function to find the minimum
# number to steps to reduce N to 0
def count(n):
   
    # Dictionary for storing
    # the precomputed sum
    dp = dict()
 
    # Bases Cases
    dp[0] = 0
    dp[1] = 1
 
    # Check if n is not in dp then
    # only call the function so as
    # to reduce no of recursive calls
    if n not in dp:
        dp[n] = 1 + min(n % 2 + count(n//2), n % 3 + count(n//3))
 
    # Return the answer
    return dp[n]
 
 
# Driver Code
 
# Given Number N
N = 6
 
# Function Call
print(str(count(N)))

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG{
     
// Function to find the minimum
// number to steps to reduce N to 0
static int count(int n)
{   
    // Dictionary for storing
    // the precomputed sum
    Dictionary<int,
               int> dp = new Dictionary<int,
                                        int>();
 
    // Bases Cases
    dp.Add(0, 0);
    dp.Add(1, 1);
 
    // Check if n is not in dp then
    // only call the function so as
    // to reduce no of recursive calls
    if (!dp.ContainsKey(n))
        dp.Add(n, 1 + Math.Min(n % 2 + count(n / 2),
                               n % 3 + count(n / 3)));
 
    // Return the answer
    return dp[n];
}
 
// Driver Code
public static void Main(String[] args)
{   
    // Given number N
    int N = 6;
 
    // Function call
    Console.WriteLine(String.Join("",
                                  (count(N))));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// JavaScript program for
// the above approach
 
// Function to find the minimum
// number to steps to reduce N to 0
function count(n)
{
  // Dictionary for storing
  // the precomputed sum
  var dp = new Map();
 
  // Bases Cases
  dp.set(0, 0);
  dp.set(1, 1);
 
  // Check if n is not in dp then
  // only call the function so as
  // to reduce no of recursive calls
  if (!dp.has(n))
    dp.set(n, 1 + Math.min(n % 2 +
                    count(parseInt(n / 2)), n % 3 +
                    count(parseInt(n / 3))));
 
  // Return the answer
  return dp.get(n);
}
 
// Driver Code
 
// Given number N
var N = 6;
 
// Function call
document.write( count(N));
 
</script>
Producción: 

3

Complejidad de tiempo: O (log N), donde N representa el número entero dado.
Espacio auxiliar: O(N), donde N representa el entero dado.

Publicación traducida automáticamente

Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *