## Introduction

In this blog, we will discuss a backtracking problem that has been asked frequently in Interviews and also is one of the most critical sets of backtracking algorithms.

The problem is to Minimize operations to transform A to B by multiplying by 2 or appending 1 to it.

Before we proceed, we must know what backtracking is?

Backtracking is an algorithmic technique for solving the recursive problem by building every possible solution incrementally and removing those answers that fail to satisfy the problem’s constraints at any time.

To make it more transparent, say, for example, a girl named Neha wants to choose a boy to marry. She has three options: Ram, Shyam and Sams. Now she decides to spend some time with each of them and then decide. Spending time with Ram makes her aware that he is too rude to handle, so she decides not to marry him. Then, she went to Shyam and realised that he was not interested in her. At last, after spending time with Sams, she realised that he fulfils all her constraints and so she decides to marry him. Here we have used the concept of backtracking.

Now let’s look at the problem.

### Problem Statement

We are given a current number, A and a target number, B. We need to reach B from A by multiplying A by 2 or appending 1 to A and returning the minimum number of operations to reach B.

### Sample Example

Say, for example the current number is 2, and the target number is 162.

First, 2*2=4.

Second, 4*2=8.

Third, 8*10+1=81.

Fourth, 81*2=162.

So in **four** operations, we can reach our target.

## Approach

If our given current number is greater than our target number, return -1.

⬇

If our given current number equals at each position the target number, return 0.

⬇

If the count of minimum operations required to change the current number to the target number is already memoised, then return the number.

⬇

Find the minimum count of operations required if the current element gets multiplied by 2.

⬇

Find the minimum count of operations required if the 1 is appended to the right of the current element.

⬇

If it is not possible to reach the target value from the current element, then return -1.

⬇

Return the minimum number of operations.

This is the most optimised approach using backtracking.

Till now, I guess you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try.

If you were not able to solve it, don’t be sad.

Please have a look at the algorithm, and then again, you must give it a try.

### PseudoCode

**Algorithm**

___________________________________________________________________

**procedure** minOperations(int cur, int B, unordered_map<int, int>& dp):

___________________________________________________________________

**1.** if cur > B:

return INT_MAX

**2**. if cur == B:

return 0

**3.** if dp.count(cur):

return dp[cur]

**4.** ans1 = minOperations(cur * 2, B, dp)

**5. ** ans2 = minOperations(cur * 10 + 1, B, dp)

**6.** if min(ans1, ans2) == INT_MAX:

return dp[cur] = INT_MAX

**7. ** return dp[cur] = min(ans1, ans2) + 1

**8. end procedure**

___________________________________________________________________

Also see, __Euclid GCD Algorithm__