Do you think IIT Guwahati certified course can help you in your career?
Introduction
With interview season on the head, we all need to tie our seat belts and start practicing as many data Structures and algorithms problems as possible. Topics like trees and graphs have an extra hipe, but simple issues must be solved. Today, we will discuss a situation that falls into pure logic or mathematics. So let's look into the problem in detail.
Problem Statement
You are given two integers, ‘N’ and ‘M’. You must find the minimum number of moves to change ‘N’ to ‘M’ using only one operation.
Operation
You can add any divisor of ‘N’ to ‘N’ except one and the number itself.
If there’s no such solution, then return -1.
Example
Input
N = 4
M = 30
Output
6
Explanation
The Moves will be = 4->6 ->8 ->12 ->18 ->24 ->30
Intuition
The best way to find out the shortest path to reach ‘M’ by adding divisors to ‘N’ would be to try all paths possible. The length of the path that fastest takes you to ‘M’ will be returned. The catch to this problem is that although it seems like a maths problem, it can be solved using a graph. In this graph, each node will be the value that ‘N’ can take by adding divisors to it, and we’ll return the length of the path when we reach a node whose value is ‘M.’
We can use a BFS to determine the shortest route. Let's use an example to better grasp this.
Approach
We'll solve this problem by using BFS on a graph in this approach. The starting node value will be 'N', and the destination node will be 'M'. And each intermediate node value will be determined by adding the divisors of the current node value. Let's see how the algorithm works.
Algorithm
Initialize a VISITED vector to store whether the node has been visited or not. So 'VISITED[i] = true if it's been visited before and 'VISITED[i] = false' if we visit the node for the first time.
Next, we initialize a queue, 'Q', for BFS and a variable, 'COUNT = 0', to store the length of the path.
Then insert the starting node, i.e., ‘N.’
Now loop through the queue until it’s not empty and iterate through all the current level nodes.
If the current node value equals ‘M,’ then return ‘COUNT’.
And for each node value, ‘X’ iterates over all divisors, and if it’s not been visited before.
At last, return -1, if there’s no path between ‘N’ and ‘M’.
Now that we’ve discussed the algorithm let’s code it.
C++ implementation
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Function to find the minimum moves to make N equals M by repeated addition of divisors.
int countMinOperations(int n, int m)
{
//Initialize vector 'VISITED' to store whether the node is visited or not.
vector<bool> visited(m + 1, false);
// Declare a 'Q' for BFS.
queue<int> Q;
// Declare 'COUNT' to store the length of the path.
int count = 0;
// Next, we push the starting node value, i.e., 'N'.
Q.push(n);
visited[n] = true;
// Loop until 'Q' is not empty.
while (!Q.empty())
{
int sz = Q.size();
while (sz--)
{
int current = Q.front();
Q.pop();
if (current == m)
{
return count;
}
// Iterate on the divisors.
for (int i = 2; i * i <= current; i++)
{
// If 'i' is a factor of 'CURRENT'.
if (current % i == 0)
{
// If 'CURRENT + i < M'.
if (current + i <= m && !visited[current + i])
{
Q.push(current + i);
visited[current + i] = true;
}
// If 'CURRENT + CURRENT / i < M'.
if (current + current / i <= m && !visited[current + current / i])
{
Q.push(current + current / i);
visited[current + current / i] = true;
}
}
}
}
count++;
}
// If there's no path from 'N' to 'M', return -1.
return -1;
}
int main()
{
int n, m;
cout << "Enter the values of N and M:";
cin >> n >> m;
int minOperation = countMinOperations(n, m);
cout << "Minimum moves to make N equals M by repeated addition of divisors is: " << minOperation << endl;
return 0;
}
Input
Enter the values of N and M: 14 58
Output
Minimum moves to make N equals M by repeated addition of divisors is: 5
Complexity
Time complexity
O ( N * sqrt( N ) ): Where N is the given Number
Reason: As for each vertex we are finding factors of the number which will take additional sqrt(n) time complexity.
Space Complexity
O(N): Where N is the given Number
Reason: As we are using a visited array for our traversal, the space occupied by the array is N. As we are moving from n to m.
Frequently Asked Questions
Is the queue FIFO or LIFO?
The First In First Out (FIFO) principle, which states that the element added to the list first is the one withdrawn from the list, is followed by the queue data structure. Enqueue operations and dequeue operations are terms used to describe adding and removing elements from queues, respectively.
Why is stack quicker than queue?
When using a queue, the entire queue must be relocated each time the first entry is popped. When you pop the last piece in a stack, you don't need to move it. So, the stack ought to be quicker. The queue can, however, be implemented differently.
What is the Breadth-First Search?
The Breadth-First Search algorithm searches a tree data structure for a node that meets a set of criteria. It begins at the tree’s root and investigates all nodes at the current depth level before moving on to nodes at the next depth level.
What is the best case time complexity for finding the Breadth-First Search in a Graph?
When only a single or no vertice is present in the graph, the best-case time complexity for finding Breadth-First Search is O(1).
What is the time complexity of the BFS algorithm?
The BFS algorithm has a time complexity of O(V+E) when using the adjacency list because each node is visited once, and O(V^2) when using the adjacency matrix.
Conclusion
In this blog, we have learned about the problem Minimum Moves to Make N Equals M by Repeated Addition of Divisors in the language C++ and also seen its time and space complexity.
Please refer to our guided pathways on Code studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses, and use the accessible sample exams and questions as a guide. For placement preparations, look at the interview experiences and interview package.
If you find any problems, please comment. We will love to answer your questions.
40+ registered 
