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:-
- 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.
- We will initially push the smaller number(let us say N) to the queue and mark it to be visited.
- 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.
- After each iteration, we will increment the ans.
- At any moment if the element popped from the queue is equal to M, we will return ans.
- 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.
568+ registered 
