# Minimum cost to reduce A and B to 0 using square root or divide by 2

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:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:A = 2, B = 2Output:4Explanation:

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 = 16Output: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)**.

- Minimum cost if
- Find the minimum of these three values and memoize it while returning from the current recursive call.

- First, check if the value of
- 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 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 recusrive 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

`// 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 recusrive 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 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 recusrive 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#

`// 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 recusrive 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 0` `function` `getMinOperations(A, B, prevA, prevB, dp) {` ` ` `// If both A and B doesn't change in` ` ` `// this recusrive 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>` |

**Output**

7

**Time Complexity: **O(max(A, B)^2)**Auxiliary Space: **O(max(A, B)^2)