Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction:
2.
Approach:
3.
Approach 2:
4.
FAQs
5.
Key Takeaways:
Last Updated: Mar 27, 2024

# Minimum moves to make M and N equal by repeated addition of divisors except 1

Nishant Rana
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

## Introduction:

We are given two integers M and N. We need to output the minimum moves to make M and N equal. If it is impossible to make them equal, then output -1. In one operation we can add any divisor of the current number(N) to it except 1 and itself(N).

Let us see a few examples:-

Input 1:

N: 6

M: 18

Output 1:

3

Explanation 1:

Minimum moves to make M and N equal are:-

6 + 3(divisor of 6) => 9

9 + 3(divisor of 3) => 12

12 + 6(divisor of 12) => 18

Input 2:

N: 10

M: 33

Output 2:

4

Explanation 2:

Minimum moves to make M and N equal are:-

10 + 5(divisor of 10) => 15

15 + 5(divisor of 15) => 20

20 + 2(divisor of 20) => 22

22 + 11(divisor of 22) => 33

Input 3:

N: 5

M: 10

Output 2:

-1

Explanation 2:

We can not reach N to M because 5 is a prime number and it has no divisor except 1 and 5 which are not allowed to add.

## Approach:

We will use the BFS algorithm to solve this problem.

We will consider that N is the smaller Number. We will start from N and try to make this number equal to M. We need to try out all the possible states. For this, we can use the BFS algorithm using which we will push all the states to the queue which we can reach from the current state. We can also do this using DFS Algorithm but in this blog, we will be discussing the BFS approach.

We will be following these steps:-

1. We will initialize a Queue and a visited array to mark the numbers we have visited. We will also keep the ans variable which will store the minimum operations required.
2. We will initially push the smaller number(let us say N) to the queue and mark it to be visited.
3. We will run the BFS algorithm till the queue is not empty and for each number in the queue, we will traverse its divisors and push (currentNumber + divisor) to the queue if it is not visited and less than equal to M.
4. After each iteration, we will increment the ans.
5. At any moment if the element popped from the queue is equal to M, we will return ans.
6. If we come out of the while loop of the BFS, we will return -1.

Refer to the below implementation of the above approach.

Time Complexity: O((M-N) * sqrt(M))

The time complexity of the above approach used to find the minimum moves to make M and N equal is O((M-N) * sqrt(M)) because in the worst case we will make (M-N) iterations of the queue and for each iteration, we are running a for loop of O(sqrt(M)) time.

Space Complexity: O(M)

The space complexity of the above approach used to find the minimum moves to make M and N equal is O(M) because we are maintaining a queue and visited array of size M.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Approach 2:

We will use the recursive approach to solve this problem. Similar to the previous approach we will try to make the smaller number(M) equal to the larger number(N) by using the recursion. At any recursive call, func(N, M) we will consider all the divisors of M and add each divisor and call the recursive function for func(N, M+divisor). As soon as M and N become equal we will return.

In the above approach, there will overlapping subproblems as you can see in the following diagram.

In the above recursion tree, we can see that func(12, 18) is getting calculated twice.

Hence, we will memoize our code to reduce the Time Complexity.

Refer to the below implementation of the above approach.

Output : 3

Time Complexity: O(N * sqrt(M))

The time complexity of the above approach used to find the minimum moves to make M and N equal is O(N * sqrt(M)) because in the worst case we will make N recursive calls and for each recursive call, we are running an sqrt(M) loop to find the divisors of M.

Space Complexity: O(M)

The space complexity of the above approach used to find the minimum moves to make M and N equal is O(M) because we are maintaining a DP array to memoize the code.

## FAQs

1. What will be the answer if the smaller number among N and M is a prime number?
In this case, the answer will be -1 because we canâ€™t add any divisor of the prime number as in the question it is already mentioned we canâ€™t add 1 and itself.

2. What is the time complexity for the optimized approach?
The time complexity of the optimized approach is O((M-N) * sqrt(M)) because in the worst case we will make (M-N) iterations of the queue and for each iteration, we are running a for loop of O(sqrt(M)) time.

3. Why are we not pushing the element if cur+divisor > M?
It is never optimal to push the greater element than M because in one operation we can only add and a bigger number will never become equal to the smaller number by adding something to it.

## Key Takeaways:

In this blog, we have covered the following things:

1. We first discussed the approach to finding the Minimum moves to make M and N equal by repeated addition of divisors except 1.
2. Then we saw how to implement the approach discussed to find the Minimum moves to make M and N equal by repeated addition of divisors except 1.

If you want to learn more about Graphs and want to practice some questions which require you to take your basic knowledge on Graphs a notch higher, then you can visit our Guided Path for Graphs

Check out this problem - Count Ways To Reach The Nth Stair

Until then, All the best for your future endeavors, and Keep Coding.

Live masterclass