What is memorization?

Answer) This is a technique that stores the result for faster and easier coding. Each time the value need not be calculated.

When is memorization used?

Answer)It is used for recursive and for heavy computing functions.

How to apply memorization?

Answer)Declare and use hashmaps. Add a base condition to return.

Table of contents

Introduction

1.1.

Problem Statement

1.2.

Sample Example

Approach

2.1.

PseudoCode

Implementation in C++

3.1.

Complexity Analysis

Frequently Asked Questions

Key Takeaways

Last Updated: Mar 27, 2024

Medium

Minimize operations to transform A to B by multiplying by 2 or appending 1 to it

Author Urwashi Priya

Do you think IIT Guwahati certified course can help you in your career?

Yes

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.

Coding Ninjas Studio

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

Implementation in C++

// C++ code to Minimize operations to transform A to B by multiplying by 2 or appending 1 to it
#include <bits/stdc++.h>
using namespace std;
// finding the minimum count of operations to transform current element to target
int minOperations(int cur, int B, unordered_map<int, int> &dp)
{
    // base condition: if our given current element is greater than our target element
    if (cur > B)
    {
        return INT_MAX;
    }
    
    // if our given current number equals the target element
    if (cur == B)
    {
        return 0;
    }
    
    // If the number of operations required is already memoised then return the count
    if (dp.count(cur))
    {
        return dp[cur];
    }
    
    // Minimum count of operations required if our current element is multiplied by 2
    int ans1 = minOperations(cur * 2, B, dp);
    
    // Minimum count of operations required if the 1 is appended to the right of our current element
    int ans2 = minOperations(cur * 10 + 1, B, dp);
    
    // If it's not possible to reach our target value from the current element then return -1
    if (min(ans1, ans2) == INT_MAX)
    {
        return dp[cur] = INT_MAX;
    }
    
    // Returning the minimum number of operations
    return dp[cur] = min(ans1, ans2) + 1;
}

int main()
{
    int A, B;
    cin >> A >> B;
    unordered_map<int, int> dp;
    int ans = minOperations(A, B, dp);
    if (ans == INT_MAX)
    {
        cout << -1;
    }
    else
    {
        cout << ans;
    }
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Sample Input: 
2 162
Sample Output:
4

Complexity Analysis

Time Complexity: O(log2 B*log10 B)

Analysing Time Complexity:

As we know, two operations can be formed, either multiply by 2 which takes O(log2 B) time or multiply by 10 and add 1 which takes O(log10 B) time.

Space complexity: O(max(log2 B, log10 B))

8 Queens Problem Using Backtracking

Frequently Asked Questions

What is memorization?
Answer) This is a technique that stores the result for faster and easier coding. Each time the value need not be calculated.
When is memorization used?
Answer)It is used for recursive and for heavy computing functions.
How to apply memorization?
Answer)Declare and use hashmaps. Add a base condition to return.

Key Takeaways

This article taught us to Minimize operations to transform A to B by multiplying by 2 or appending 1 to it by approaching the problem using the backtracking method. We discussed its implementation using illustrations, pseudocode, and then optimised proper code.

We hope you could take away all critical techniques like analysing problems by walking over the execution of the examples and finding out the recursive pattern followed in most backtracking problems.
Now, we recommend you practice problem sets based on stacks to master your fundamentals. You can get a wide range of questions similar to this problem on Coding Ninjas Studio.

It's not the end. Must solve the problem of similar types.

Recommended Problems:

Happy Coding.