Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
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

Author 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.

 

//Function to find the minimum moves to make M and N equal
static int countOperations(int N, int M)
{
    
    // vis array to check if the current number is visited or not.
    boolean[] vis = new boolean[M+1];
    Arrays.fill(vis, false);
    
    Queue<Integer> Q = new LinkedList<>();
    Q.add(N);
    vis[N] = true;
    int ans = 0;
    
    // Running the while loop till the queue is not empty.
    while (!Q.isEmpty())
    {
        int size = Q.size();
 
        while(size-->0){
            int cur = Q.remove();
            
            //If we reached M.
            if(cur == M){
                return ans;
            }
            
            // Iterating to search for the divisors of cur.
            for(int i = 2; i * i <= cur; i++){
            
                //If i is one of the factors of cur.
                if (cur % i == 0)
                {
                    
                    // If cur + i is less than equal to M and not visited.
                    if (cur + i <= M && !vis[cur + i]){
                        Q.add(cur + i);
                        vis[cur + i] = true;
                    }
                    
                    /*
                      If cur + cur/i is less than M
                      and is not visited.
                    */
                    if (cur + cur / i <= M && !vis[cur + cur / i]){
                        Q.add(cur + cur / i);
                        vis[cur + cur / i] = true;
                    }
                }
            }
        }
        ans++;
    }
    
    // Not possible
    return -1;
}

 

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.

 

import java.util.*;
 
public class Main {
 
    static int INF = 10000007;
 
    /*
      This function will return the
      Minimum moves to make M and N
      equal to each other.
    */
    public static int minimumSteps(int M, int N, int DP[])
    {

        // Base Case
        if (N == M)
            return 0;
 
        // We will return if M exceed N
        if (M > N)
            return INF;
 
        int minimumCost = INF;
 
        /*
          Return from here if the
          current state is already
          calculated.
        */
        if (DP[M] != INF)
            return DP[M];
          
        //Iterating the divisors of M
        for (int i = 2; i*i < M; i += 1) {
 
            /*
              If i is the divisor of M
              then find the minimum cost
              to make M and N equal.
            */
            if (M % i == 0) {
                minimumCost = Math.min(minimumCost, 1 + minimumSteps(M + i, N, DP));
              
                if(M/i != i){
                    minimumCost = Math.min(minimumCost, 1 + minimumSteps(M + M/i, N, DP));
                }
            }
        }
 
        // Return minimumCost
        return DP[M] = minimumCost;
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = 6;
        int M = 18;
        
        int DP[] = new int[19];
        Arrays.fill(DP, INF);
        
        System.out.println(minimumSteps(N, M, DP));
    }
}

 

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.







 

Previous article
Maximize Score by Multiplying Elements of Given Array with Given Multipliers
Next article
Count of subsets with sum equal to X
Live masterclass