Minimice las operaciones para transformar A en B multiplicando por 2 o agregándole 1

Posted on by Rudeus Greyrat

Dados dos números A y B , la tarea es encontrar el número mínimo de las siguientes operaciones para transformar A en B :

  1. Multiplique el número actual por 2 (es decir, reemplace el número X por 2X )
  2. Agregue el dígito 1 a la derecha del número actual (es decir, reemplace el número X por 10X + 1 ).

Imprime -1 si no es posible transformar A en B .

Ejemplos:

Entrada: A = 2, B = 162
Salida: 4
Explicación: 
Operación 1: Cambie A a 2*A, entonces A=2*2=4
Operación 2: Cambie A a 2*A, entonces A=2*4=8 .
Operación 3: Cambiar A a 10*A+1, entonces A=10*8+1=81
Operación 4: Cambiar A a 2*A, entonces A=2*81=162

Entrada: A = 4, B = 42
Salida: -1

Enfoque: este problema se puede resolver generando recursivamente todas las soluciones posibles y luego eligiendo la mínima de ellas. Ahora, para resolver este problema, siga los siguientes pasos:

  1. Cree una función recursiva minOperation que aceptará tres parámetros que son el número actual (cur) , el número objetivo (B) y un mapa (dp) para memorizar el resultado devuelto. Esta función devolverá el número de operaciones mínimas necesarias para transformar el número actual en el número de destino.
  2. Inicialmente pase A como cur , B y un mapa vacío dp en minOperations .
  3. Ahora en cada llamada recursiva:
    1. Compruebe si cur es mayor que B , si lo es, devuelva INT_MAX ya que no es posible transformar el número actual en B .
    2. Compruebe si cur es igual a B , si lo es, devuelva 0.
    3. También verifique si el resultado de esta llamada de función ya está almacenado en el mapa dp . Si es así, devuélvelo desde allí.
    4. De lo contrario, vuelva a llamar a esta función para (cur* 2) y (cur*10+1) y devuelva el resultado mínimo de estos dos después de memorizar.
  4. Ahora, si la llamada inicial devuelve INT_MAX, imprima -1 ya que no es posible transformar A en B. De lo contrario, la respuesta es el número entero devuelto por esta llamada de función.

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

C++

// C++ code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find
// the minimum number of operations
// needed to transform A to B
int minOperations(int cur, int B,
                  unordered_map<int, int>& dp)
{
 
    // If current number
    // is greater than target
    if (cur > B) {
        return INT_MAX;
    }
 
    // if current number
    // is equal to the target
    if (cur == B) {
        return 0;
    }
 
    // If the number of minimum
    // operations required to
    // change the current number
    // to the target number
    // is already memoised
    if (dp.count(cur)) {
        return dp[cur];
    }
 
    // Minimum number of operations
    // required if the current element
    // gets multiplied by 2
    int ans1 = minOperations(cur * 2, B, dp);
 
    // Minimum number of operations
    // required if the 1 is appended to
    // the right of the current element
    int ans2 = minOperations(cur * 10 + 1, B, dp);
 
    // If it is not possible
    // to reach the target value
    // from the current element
    if (min(ans1, ans2) == INT_MAX) {
        return dp[cur] = INT_MAX;
    }
 
    // Returning the minimum
    // number of operations
    return dp[cur] = min(ans1, ans2) + 1;
}
 
// Driver Code
int main()
{
    int A = 2, B = 162;
    unordered_map<int, int> dp;
    int ans = minOperations(A, B, dp);
 
    // If A cannot be transformed to B
    if (ans == INT_MAX) {
        cout << -1;
    }
 
    else {
        cout << ans;
    }
}

Java

// Java code for the above approach
import java.util.HashMap;
class GFG {
 
  // Function to find
  // the minimum number of operations
  // needed to transform A to B
  static int minOperations(int cur, int B, HashMap<Integer, Integer> dp) {
 
    // If current number
    // is greater than target
    if (cur > B) {
      return Integer.MAX_VALUE;
    }
 
    // if current number
    // is equal to the target
    if (cur == B) {
      return 0;
    }
 
    // If the number of minimum
    // operations required to
    // change the current number
    // to the target number
    // is already memoised
    if (dp.containsKey(cur)) {
      return dp.get(cur);
    }
 
    // Minimum number of operations
    // required if the current element
    // gets multiplied by 2
    int ans1 = minOperations(cur * 2, B, dp);
 
    // Minimum number of operations
    // required if the 1 is appended to
    // the right of the current element
    int ans2 = minOperations(cur * 10 + 1, B, dp);
 
    // If it is not possible
    // to reach the target value
    // from the current element
    if (Math.min(ans1, ans2) == Integer.MAX_VALUE) {
      dp.put(cur, Integer.MAX_VALUE);
      return dp.get(cur);
    }
 
    // Returning the minimum
    // number of operations
    dp.put(cur, Math.min(ans1, ans2) + 1);
    return dp.get(cur);
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int A = 2, B = 162;
    HashMap<Integer, Integer> dp = new HashMap<Integer, Integer>();
    int ans = minOperations(A, B, dp);
 
    // If A cannot be transformed to B
    if (ans == Integer.MAX_VALUE) {
      System.out.println(-1);
    }
 
    else {
      System.out.println(ans);
    }
  }
}
 
// This code is contributed by gfgking.

Python3

# Python 3 code for the above approach
import sys
# Function to find
# the minimum number of operations
# needed to transform A to B
 
 
def minOperations(cur, B,
                  dp):
 
    # If current number
    # is greater than target
    if (cur > B):
        return sys.maxsize
 
    # if current number
    # is equal to the target
    if (cur == B):
        return 0
 
    # If the number of minimum
    # operations required to
    # change the current number
    # to the target number
    # is already memoised
    if (cur in dp):
        return dp[cur]
 
    # Minimum number of operations
    # required if the current element
    # gets multiplied by 2
    ans1 = minOperations(cur * 2, B, dp)
 
    # Minimum number of operations
    # required if the 1 is appended to
    # the right of the current element
    ans2 = minOperations(cur * 10 + 1, B, dp)
 
    # If it is not possible
    # to reach the target value
    # from the current element
    if (min(ans1, ans2) == sys.maxsize):
        dp[cur] = sys.maxsize
        return dp[cur]
 
    # Returning the minimum
    # number of operations
    dp[cur] = min(ans1, ans2) + 1
    return dp[cur]
 
 
# Driver Code
if __name__ == "__main__":
 
    A = 2
    B = 162
    dp = {}
    ans = minOperations(A, B, dp)
 
    # If A cannot be transformed to B
    if (ans == sys.maxsize):
        print(-1)
    else:
        print(ans)
 
        # This code is contributed by ukasp.

C#

// C# code for the above approach
using System;
using System.Collections.Generic;
class GFG {
 
    // Function to find
    // the minimum number of operations
    // needed to transform A to B
    static int minOperations(int cur, int B,
                             Dictionary<int, int> dp)
    {
 
        // If current number
        // is greater than target
        if (cur > B) {
            return Int32.MaxValue;
        }
 
        // if current number
        // is equal to the target
        if (cur == B) {
            return 0;
        }
 
        // If the number of minimum
        // operations required to
        // change the current number
        // to the target number
        // is already memoised
        if (dp.ContainsKey(cur)) {
            return dp[cur];
        }
 
        // Minimum number of operations
        // required if the current element
        // gets multiplied by 2
        int ans1 = minOperations(cur * 2, B, dp);
 
        // Minimum number of operations
        // required if the 1 is appended to
        // the right of the current element
        int ans2 = minOperations(cur * 10 + 1, B, dp);
 
        // If it is not possible
        // to reach the target value
        // from the current element
        if (Math.Min(ans1, ans2) == Int32.MaxValue) {
            dp[cur] = Int32.MaxValue;
            return dp[cur];
        }
 
        // Returning the minimum
        // number of operations
        dp[cur] = Math.Min(ans1, ans2) + 1;
        return dp[cur];
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int A = 2, B = 162;
        Dictionary<int, int> dp
            = new Dictionary<int, int>();
        int ans = minOperations(A, B, dp);
 
        // If A cannot be transformed to B
        if (ans == Int32.MaxValue) {
            Console.WriteLine(-1);
        }
 
        else {
            Console.WriteLine(ans);
        }
    }
}
 
// This code is contributed by gaurav01.

Javascript

<script>
      // JavaScript code for the above approach
 
      // Function to find
      // the minimum number of operations
      // needed to transform A to B
      function minOperations(cur, B,
          dp) {
 
          // If current number
          // is greater than target
          if (cur > B) {
              return Number.MAX_VALUE;
          }
 
          // if current number
          // is equal to the target
          if (cur == B) {
              return 0;
          }
 
          // If the number of minimum
          // operations required to
          // change the current number
          // to the target number
          // is already memoised
          if (dp[cur] != 0) {
              return dp[cur];
          }
 
          // Minimum number of operations
          // required if the current element
          // gets multiplied by 2
          let ans1 = minOperations(cur * 2, B, dp);
 
          // Minimum number of operations
          // required if the 1 is appended to
          // the right of the current element
          let ans2 = minOperations(cur * 10 + 1, B, dp);
 
          // If it is not possible
          // to reach the target value
          // from the current element
          if (Math.min(ans1, ans2) == Number.MAX_VALUE) {
              return dp[cur] = Number.MAX_VALUE;
          }
 
          // Returning the minimum
          // number of operations
          return dp[cur] = Math.min(ans1, ans2) + 1;
      }
 
      // Driver Code
      let A = 2, B = 162;
      let dp = new Array(100000).fill(0);
      let ans = minOperations(A, B, dp);
 
      // If A cannot be transformed to B
      if (ans == Number.MAX_VALUE) {
          document.write(-1);
      }
 
      else {
          document.write(ans);
      }
 
// This code is contributed by Potta Lokesh
  </script>
Producción

4

 
 Complejidad de tiempo: O(log 2 B*log 10 B) 
Espacio auxiliar: O(max(log 2 B, log 10 B))

Publicación traducida automáticamente

Artículo escrito por Code_r 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 *