Given two integers A and B, the task is to convert the given two integers to zero at minimal cost by performing the following two types of operations:
- Replace both integers A and B by the square root of the product of A and B. This operation will cost 2 units.
- Replace A by A/2 or B by B/2 respectively. This operation will cost 1 unit.
Example:
Input: A = 2, B = 2
Output: 4
Explanation:
Operation 1: Apply first operation on A, making A=1, B=2. Cost=1
Operation 2: Apply first operation again on A, making A=0, B=2. Cost=2
Operation 3: Apply second operation on both A and B, making A=0, B=0. Cost=4.Input: A = 53, B = 16
Output: 7
Approach:
This problem can be solved by exploring all possibilities using a recursive tree and then memoizing the solution in a matrix. To solve this problem follow the below steps:
- Create a function getMinOperations with five parameters that are A, B, prevA, prevB, and a dp matrix, here prevA and prevB are the previous value of A and B. This function will return the minimum cost required to make A and B to zero.
- Now, call this function initially with arguments, A, B, prevA = -1, prevB = -1 and dp.
- In each call:
- First, check if the value of A and B is equal to the value of prevA and prevB. If they are, return INT_MAX from this call as this call is resulting in no change in the values of A and B and therefore will resulting in an infinite recursive loop.
- Check for the base case that is both A and B are zero. If they are, return 0 from this call because the minimum cost to convert A and B to zero is 0 at this stage.
- Also, check if this recursive call is already memorized in the dp matrix. If it is, then return the value from the matrix.
- Now, the answer of every recursive call is the minimum of the answers provided by three subproblems:
- Minimum cost if A is reduced to A/2.
- Minimum cost if B is reduced to B/2.
- Minimum cost if both A and B is reduced to sqrt(A*B).
- Find the minimum of these three values and memoize it while returning from the current recursive call.
- The function will return the minimum cost after all recursive calls are made.
Below is the implementation of the above approach:
C++
// 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 0int 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 Codeint 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
// Java program for the above approachimport 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 |
Python3
# Python program for the above approachimport math as Math# Function to return the minimum cost# of converting A and B to 0def 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 CodeA = 53B = 16mx = 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#
// C# program for the above approachusing 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. |
Javascript
<script>// javascript program for the above approach// Function to return the minimum cost// of converting A and B to 0function 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 Codelet 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> |
Output
7
Time Complexity: O(max(A, B)^2)
Auxiliary Space: O(max(A, B)^2)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a 2D DP to store the solution of the subproblems and initialize it with 0.
- Initialize the DP with base cases
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP
- Create three variables ans1, ans2, and ans3 to keep track of answers in 3 different conditions.
- update the current value of DP minimum of ans1, ans2 and ans3.
- At last return final answer stored in dp[A][B].
Implementation :
C++
// 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 0int getMinOperations(int A, int B) { int mx = max(A, B); // Initialize dp to store // computations of subproblems vector<vector<int>> dp(mx + 1, vector<int>(mx + 1, 0)); // iterate over Dp to get the current value // from previous computation stored in DP for (int i = 1; i <= A; i++) { for (int j = 1; j <= B; j++) { if (i == 1 && j == 1) { dp[i][j] = 0; } else { // intialize three answers variables int ans1 = INT_MAX, ans2 = INT_MAX, ans3 = INT_MAX; if (i >= 2) { ans1 = dp[i/2][j]; if (ans1 != INT_MAX) { ans1 += 1; } } if (j >= 2) { ans2 = dp[i][j/2]; if (ans2 != INT_MAX) { ans2 += 1; } } int s = sqrt(i*j); if (s*s == i*j) { ans3 = dp[s][s]; if (ans3 != INT_MAX) { ans3 += 2; } } // update DP dp[i][j] = min({ ans1, ans2, ans3 }); } } } // return answer return dp[A][B];}// Driver Codeint main() { int A = 53, B = 16; // function call cout << getMinOperations(A, B); return 0;}// this code is contributed by bhardwajji |
Java
import java.util.*;public class Main{ // Function to return the minimum cost // of converting A and B to 0 static int getMinOperations(int A, int B) { int mx = Math.max(A, B); // Initialize dp to store // computations of subproblems int[][] dp = new int[mx + 1][mx + 1]; for (int i = 1; i <= mx; i++) { Arrays.fill(dp[i], 0); } // iterate over Dp to get the current value // from previous computation stored in DP for (int i = 1; i <= A; i++) { for (int j = 1; j <= B; j++) { if (i == 1 && j == 1) { dp[i][j] = 0; } else { // intialize three answers variables int ans1 = Integer.MAX_VALUE, ans2 = Integer.MAX_VALUE, ans3 = Integer.MAX_VALUE; if (i >= 2) { ans1 = dp[i/2][j]; if (ans1 != Integer.MAX_VALUE) { ans1 += 1; } } if (j >= 2) { ans2 = dp[i][j/2]; if (ans2 != Integer.MAX_VALUE) { ans2 += 1; } } int s = (int)Math.sqrt(i*j); if (s*s == i*j) { ans3 = dp[s][s]; if (ans3 != Integer.MAX_VALUE) { ans3 += 2; } } // update DP dp[i][j] = Math.min(Math.min(ans1, ans2), ans3); } } } // return answer return dp[A][B]; } // Driver Code public static void main(String[] args) { int A = 53, B = 16; // function call System.out.println(getMinOperations(A, B)); }} |
Python3
import math# Function to return the minimum cost# of converting A and B to 0def getMinOperations(A, B): mx = max(A, B) # Initialize dp to store # computations of subproblems dp = [[0 for j in range(mx+1)] for i in range(mx+1)] # iterate over Dp to get the current value # from previous computation stored in DP for i in range(1, A+1): for j in range(1, B+1): if (i == 1 and j == 1): dp[i][j] = 0 else: # intialize three answers variables ans1, ans2, ans3 = math.inf, math.inf, math.inf if (i >= 2): ans1 = dp[i//2][j] if (ans1 != math.inf): ans1 += 1 if (j >= 2): ans2 = dp[i][j//2] if (ans2 != math.inf): ans2 += 1 s = int(math.sqrt(i*j)) if (s*s == i*j): ans3 = dp[s][s] if (ans3 != math.inf): ans3 += 2 # update DP dp[i][j] = min(ans1, ans2, ans3) # return answer return dp[A][B]# Driver Codeif __name__ == '__main__': A = 53 B = 16 # function call print(getMinOperations(A, B)) |
C#
using System;public class GFG { // Function to return the minimum cost // of converting A and B to 0 static int getMinOperations(int A, int B) { int mx = Math.Max(A, B); // Initialize dp to store // computations of subproblems int[, ] dp = new int[mx + 1, mx + 1]; // iterate over Dp to get the current value // from previous computation stored in DP for (int i = 1; i <= A; i++) { for (int j = 1; j <= B; j++) { if (i == 1 && j == 1) { dp[i, j] = 0; } else { // intialize three answers variables int ans1 = int.MaxValue, ans2 = int.MaxValue, ans3 = int.MaxValue; if (i >= 2) { ans1 = dp[i / 2, j]; if (ans1 != int.MaxValue) { ans1 += 1; } } if (j >= 2) { ans2 = dp[i, j / 2]; if (ans2 != int.MaxValue) { ans2 += 1; } } int s = (int)Math.Sqrt(i * j); if (s * s == i * j) { ans3 = dp[s, s]; if (ans3 != int.MaxValue) { ans3 += 2; } } // update DP dp[i, j] = Math.Min( ans1, Math.Min(ans2, ans3)); } } } // return answer return dp[A, B]; } // Driver Code public static void Main() { int A = 53; int B = 16; // function call Console.WriteLine(getMinOperations(A, B)); }} |
Javascript
// javascript program for the above approach// Function to return the minimum cost// of converting A and B to 0function getMinOperations(A, B) { let mx = Math.max(A, B); // Initialize dp to store // computations of subproblems let dp = new Array(mx + 1); for (let i = 0; i <= mx; i++) { dp[i] = new Array(mx + 1).fill(0); } // iterate over Dp to get the current value // from previous computation stored in DP for (let i = 1; i <= A; i++) { for (let j = 1; j <= B; j++) { if (i === 1 && j === 1) { dp[i][j] = 0; } else { // intialize three answers variables let ans1 = Infinity, ans2 = Infinity, ans3 = Infinity; if (i >= 2) { ans1 = dp[Math.floor(i / 2)][j]; if (ans1 !== Infinity) { ans1 += 1; } } if (j >= 2) { ans2 = dp[i][Math.floor(j / 2)]; if (ans2 !== Infinity) { ans2 += 1; } } let s = Math.floor(Math.sqrt(i * j)); if (s * s === i * j) { ans3 = dp[s][s]; if (ans3 !== Infinity) { ans3 += 2; } } // update DP dp[i][j] = Math.min(ans1, ans2, ans3); } } } // return answer return dp[A][B];}// Driver Code let A = 53, B = 16; // function call console.log(getMinOperations(A, B)); |
Output
7
Time Complexity: O(max(A, B)^2)
Auxiliary Space: O(max(A, B)^2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
