Minimum Operations to Convert Number

Algorithm

• For the implementation of BFS, take a queue, q, and push START into it.
• Take a vector to keep track of the values being pushed into the queue to avoid repetition.
• First, consider the START value, and perform every operation on it, i.e., add, subtract, and XOR, with every element of the NUMS array.
• After completing the operations, check if any of the value matches with GOAL.
• If the values don't match, check if the values lie in the range [0, 1000]. If they do, push these into the queue.
• If the queue becomes empty, there is no possible solution to our problem, so return. 

Implementation

Program

// C++ program to find the minimum number of operations to convert a number,'start' into 'goal'.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// Function to find the minimum operations to convert number.
int minimumOperations(vector<int> & nums, int start, int goal)
{
    int n = nums.size();

    // Queue to implement BFS.
    queue<int> q;

    // Vector to maintain the visited nodes.
    vector<bool> visited(1001, false);

    // Adding 'START' to the queue as a base case.
    q.push(start);
    int ans = 0;
    while (!q.empty())
    {
        int size = q.size();
        while (size--)
        {
            int x = q.front();
            q.pop();
            if (x == goal)
                return ans;

            // If 'X' is out of bound or has been visited before, there's no need to proceed with it.
            if (x > 1000 || x < 0 || visited[x] == true)
                continue;

            // Marking 'X' as visited.
            visited[x] = true;

            // If 'X' is unvisited, all the 3 operations are performed, and the value is added into the queue.
            for (int i = 0; i < nums.size(); i++)
            {
                int first = x + nums[i];
                int second = x - nums[i];
                int third = x ^ nums[i];
                q.push(first);
                q.push(second);
                q.push(third);
            }
        }

        // Operation has been performed so the value is updated.
        ans++;
    }

    // In case goal cannot be obtained from the start.
    return -1;
}

int main()
{
    int start, goal, n, a;

    // Taking user input.
    cout << "Enter the starting number: ";
    cin >> start;
    cout << "Enter the goal: ";
    cin >> goal;
    cout << "Enter the size of the array: ";
    cin >> n;

    vector<int> nums;
    cout << "Enter the integers of the array: ";
    for (int i = 0; i < n; i++)
    {
        cin >> a;
        nums.push_back(a);
    }

    // Calling the function and printing our answer.
    cout << "The minimum number of operations to convert " << start << " into " << goal << " is " << minimumOperations(nums, start, goal);
    
    return 0;
}

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

Run Code

Input

Enter the starting number: 0

Enter the goal: -4

Enter the size of the array: 3

Enter the integers of the array: 

3 5 7

Output

The minimum number of operations to convert 0 to -4 is 2.

Time Complexity

The time complexity is given by O(N*K), where N is the size of the array and K is the total number of elements that can be pushed into the queue. (1 <= K <= 1000)

There are 2 loops, the inner loop iterates, over all elements of the array of size N, and the outer loop iterates until the queue become empty, while the inner loop so the time complexity is given by O(N * K).

Space Complexity

The space complexity is given by O(K), where K is the total number of elements that can be pushed into the queue.  (1 <= K <= 1000)

Since we are taking a queue to implement BFS whose size can go up to 3 * N in the worst case and extra space of size 1001, to keep a record of the values being pushed into the queue, the space complexity is given by O(K).

 Also Read - Strong number in c

Key Takeaways

This blog discussed the problem of Minimum Operations to Convert Number and shed some light on its time and space complexity.

To learn more about Graphs and Trees, head over right now to Coding Ninjas Studio to practice problems and crack your interviews like a Ninja!

Practicing a bunch of questions is not enough in this competitive world. So go check out where you stand among your peers by taking our mock tests and see which areas need improvement.

In case of any comments or suggestions, feel free to post them in the comments section.