Costo mínimo para reducir A y B a 0 usando raíz cuadrada o dividir por 2

Dados dos enteros A y B, la tarea es convertir los dos enteros dados a cero a un costo mínimo realizando los siguientes dos tipos de operaciones: 

• Reemplaza los números enteros A y B por la raíz cuadrada del producto de A y B. Esta operación costará 2 unidades.
• Reemplace A por A/2 o B por B/2 respectivamente. Esta operación costará 1 unidad.

Ejemplo:

Entrada: A = 2, B = 2
Salida: 4
Explicación:
Operación 1: Aplicar la primera operación en A, haciendo A=1, B=2. Costo=1
Operación 2: Aplicar la primera operación nuevamente en A, haciendo A=0, B=2. Costo=2
Operación 3: Aplicar la segunda operación tanto en A como en B, haciendo A=0, B=0. Costo=4.

Entrada: A = 53, B = 16
Salida: 7

Acercarse:

Este problema se puede resolver explorando todas las posibilidades usando un árbol recursivo y luego memorizando la solución en una array. Para resolver este problema, siga los siguientes pasos:

1. Cree una función getMinOperations con cinco parámetros que son A, B,   prevA , prevB y una array dp , aquí prevA y prevB son el valor anterior de A y B. Esta función devolverá el costo mínimo requerido para hacer que A y B sean cero.
2. Ahora, llame a esta función inicialmente con argumentos, A, B, prevA = -1, prevB = -1 y dp .
3. En cada llamada:
   • Primero, verifique si el valor de A y B es igual al valor de prevA y prevB . Si lo son, devuelva INT_MAX de esta llamada, ya que esta llamada no produce ningún cambio en los valores de A y B y, por lo tanto, dará como resultado un bucle recursivo infinito.
   • Verifique que el caso base sea que tanto A como B son cero. Si lo son, devuelva 0 de esta llamada porque el costo mínimo para convertir A y B a cero es 0 en esta etapa.
   • Además, verifique si esta llamada recursiva ya está memorizada en la array dp . Si es así, devuelva el valor de la array.
   • Ahora, la respuesta de cada llamada recursiva es el mínimo de las respuestas proporcionadas por tres subproblemas:
     • Costo mínimo si A se reduce a A/2 .
     • Costo mínimo si B se reduce a B/2 .
     • Costo mínimo si tanto A como B se reducen a sqrt(A*B) .
   • Encuentre el mínimo de estos tres valores y memorícelo mientras regresa de la llamada recursiva actual.
4. La función devolverá el costo mínimo después de realizar todas las llamadas recursivas.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum cost
// of converting A and B to 0
int getMinOperations(int A, int B,
                     int prevA, int prevB,
                     vector<vector<int> >& dp)
{
 
    // If both A and B doesn't change in
    // this recursive call, then return INT_MAX
    // to save the code from going into
    // infinite loop
    if (A == prevA and B == prevB) {
        return INT_MAX;
    }
 
    // Base Case
    if (A == 0 and B == 0) {
        return 0;
    }
 
    // If the answer of this recursive call
    // is already memoised
    if (dp[A][B] != -1) {
        return dp[A][B];
    }
 
    // If A is reduced to A/2
    int ans1 = getMinOperations(
        A / 2, B, A, B, dp);
    if (ans1 != INT_MAX) {
        ans1 += 1;
    }
 
    // If B is reduced to B/2
    int ans2 = getMinOperations(
        A, B / 2, A, B, dp);
    if (ans2 != INT_MAX) {
        ans2 += 1;
    }
 
    // If both A and B is reduced to sqrt(A * B)
    int ans3 = getMinOperations(sqrt(A * B),
                                sqrt(A * B), A,
                                B, dp);
    if (ans3 != INT_MAX) {
        ans3 += 2;
    }
 
    // Return the minimum of the value given
    // by the above three subproblems, also
    // memoize the value while returning
    return dp[A][B] = min({ ans1, ans2, ans3 });
}
 
// Driver Code
int main()
{
    int A = 53, B = 16;
    int mx = max(A, B);
    vector<vector<int> > dp(
        mx + 1,
        vector<int>(mx + 1, -1));
 
    cout << getMinOperations(
        A, B, -1, -1, dp);
}

// Java program for the above approach
import java.io.*;
class GFG
{
   
    // Function to return the minimum cost
    // of converting A and B to 0
    static int getMinOperations(int A, int B, int prevA,
                                int prevB, int dp[][])
    {
 
        // If both A and B doesn't change in
        // this recursive call, then return INT_MAX
        // to save the code from going into
        // infinite loop
        if (A == prevA && B == prevB) {
            return Integer.MAX_VALUE;
        }
 
        // Base Case
        if (A == 0 && B == 0) {
            return 0;
        }
 
        // If the answer of this recursive call
        // is already memoised
        if (dp[A][B] != -1) {
            return dp[A][B];
        }
 
        // If A is reduced to A/2
        int ans1 = getMinOperations(A / 2, B, A, B, dp);
        if (ans1 != Integer.MAX_VALUE) {
            ans1 += 1;
        }
 
        // If B is reduced to B/2
        int ans2 = getMinOperations(A, B / 2, A, B, dp);
        if (ans2 != Integer.MAX_VALUE) {
            ans2 += 1;
        }
 
        // If both A and B is reduced to sqrt(A * B)
        int ans3 = getMinOperations((int)Math.sqrt(A * B),
                                    (int)Math.sqrt(A * B),
                                    A, B, dp);
        if (ans3 != Integer.MAX_VALUE) {
            ans3 += 2;
        }
        // Return the minimum of the value given
        // by the above three subproblems, also
        // memoize the value while returning
        return dp[A][B]
            = Math.min(ans1, Math.min(ans2, ans3));
    }
   
    // Driver Code
    public static void main(String[] args)
    {
        int A = 53, B = 16;
        int mx = Math.max(A, B);
        int dp[][] = new int[mx + 1][mx + 1];
        for (int i = 0; i <= mx; i++) {
            for (int j = 0; j <= mx; j++)
                dp[i][j] = -1;
        }
        System.out.println(
            getMinOperations(A, B, -1, -1, dp));
    }
}
 
// This code is contributed by dwivediyash

# Python program for the above approach
import math as Math
 
# Function to return the minimum cost
# of converting A and B to 0
def getMinOperations(A, B, prevA, prevB, dp):
   
  # If both A and B doesn't change in
  # this recursive call, then return INT_MAX
  # to save the code from going into
  # infinite loop
  if (A == prevA and B == prevB):
    return 10**9;
   
  # Base Case
  if (A == 0 and B == 0):
    return 0;
   
  # If the answer of this recursive call
  # is already memoised
  if (dp[A][B] != -1):
    return dp[A][B];
   
  # If A is reduced to A/2
  ans1 = getMinOperations(A // 2, B, A, B, dp);
  if (ans1 != 10**9):
    ans1 += 1;
   
  # If B is reduced to B/2
  ans2 = getMinOperations(A, B // 2, A, B, dp);
  if (ans2 != 10**9):
    ans2 += 1;
   
  # If both A and B is reduced to sqrt(A * B)
  ans3 = getMinOperations(
    Math.floor(Math.sqrt(A * B)),
    Math.floor(Math.sqrt(A * B)),
    A,
    B,
    dp
  );
  if (ans3 != 10**9):
    ans3 += 2;
   
  # Return the minimum of the value given
  # by the above three subproblems, also
  # memoize the value while returning
  dp[A][B] = min(ans1, min(ans2, ans3))
  return dp[A][B];
 
# Driver Code
A = 53
B = 16
mx = max(A, B);
dp = [[-1 for i in range(mx + 1)] for i in range(mx + 1)]
 
print(getMinOperations(A, B, -1, -1, dp));
 
# This code is contributed by gfgking.

// C# program for the above approach
using System;
using System.Collections;
class GFG
{
   
    // Function to return the minimum cost
    // of converting A and B to 0
    static int getMinOperations(int A, int B, int prevA,
                                int prevB, int [,]dp)
    {
 
        // If both A and B doesn't change in
        // this recursive call, then return INT_MAX
        // to save the code from going into
        // infinite loop
        if (A == prevA && B == prevB) {
            return Int32.MaxValue;
        }
 
        // Base Case
        if (A == 0 && B == 0) {
            return 0;
        }
 
        // If the answer of this recursive call
        // is already memoised
        if (dp[A, B] != -1) {
            return dp[A, B];
        }
 
        // If A is reduced to A/2
        int ans1 = getMinOperations(A / 2, B, A, B, dp);
        if (ans1 != Int32.MaxValue) {
            ans1 += 1;
        }
 
        // If B is reduced to B/2
        int ans2 = getMinOperations(A, B / 2, A, B, dp);
        if (ans2 != Int32.MaxValue) {
            ans2 += 1;
        }
 
        // If both A and B is reduced to sqrt(A * B)
        int ans3 = getMinOperations((int)Math.Sqrt(A * B),
                                    (int)Math.Sqrt(A * B),
                                    A, B, dp);
        if (ans3 != Int32.MaxValue) {
            ans3 += 2;
        }
        // Return the minimum of the value given
        // by the above three subproblems, also
        // memoize the value while returning
        return dp[A, B]
            = Math.Min(ans1, Math.Min(ans2, ans3));
    }
   
    // Driver Code
    public static void Main()
    {
        int A = 53, B = 16;
        int mx = Math.Max(A, B);
        int [,]dp = new int[mx + 1, mx + 1];
        for (int i = 0; i <= mx; i++) {
            for (int j = 0; j <= mx; j++)
                dp[i, j] = -1;
        }
        Console.Write(
            getMinOperations(A, B, -1, -1, dp));
    }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
// javascript program for the above approach
 
// Function to return the minimum cost
// of converting A and B to 0
function getMinOperations(A, B, prevA, prevB, dp) {
  // If both A and B doesn't change in
  // this recursive call, then return INT_MAX
  // to save the code from going into
  // infinite loop
  if (A == prevA && B == prevB) {
    return Number.MAX_SAFE_INTEGER;
  }
 
  // Base Case
  if (A == 0 && B == 0) {
    return 0;
  }
 
  // If the answer of this recursive call
  // is already memoised
  if (dp[A][B] != -1) {
    return dp[A][B];
  }
 
  // If A is reduced to A/2
  let ans1 = getMinOperations(Math.floor(A / 2), B, A, B, dp);
  if (ans1 != Number.MAX_SAFE_INTEGER) {
    ans1 += 1;
  }
 
  // If B is reduced to B/2
  let ans2 = getMinOperations(A, Math.floor(B / 2), A, B, dp);
  if (ans2 != Number.MAX_SAFE_INTEGER) {
    ans2 += 1;
  }
 
  // If both A and B is reduced to sqrt(A * B)
  let ans3 = getMinOperations(
    Math.floor(Math.sqrt(A * B)),
    Math.floor(Math.sqrt(A * B)),
    A,
    B,
    dp
  );
  if (ans3 != Number.MAX_SAFE_INTEGER) {
    ans3 += 2;
  }
 
  // Return the minimum of the value given
  // by the above three subproblems, also
  // memoize the value while returning
  return (dp[A][B] = Math.min(ans1, Math.min(ans2, ans3)));
}
 
// Driver Code
 
let A = 53,
  B = 16;
let mx = Math.max(A, B);
let dp = new Array(mx + 1).fill(0).map(() => new Array(mx + 1).fill(-1));
 
document.write(getMinOperations(A, B, -1, -1, dp));
 
// This code is contributed by saurabh_jaiswal.
</script>

7

Complejidad de tiempo: O(max(A, B)^2)
Espacio auxiliar: O(max(A, B)^2)