Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Example
2.
Approach
3.
Algorithm
4.
Implementation
4.1.
Program
4.2.
Input
4.3.
Output
5.
Time Complexity
6.
Space Complexity
7.
Key Takeaways
Last Updated: Mar 27, 2024

Minimum Operations to Convert Number

Author Ishita Chawla
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Graphs can be used to solve many problems in computer science. Graph problems include, for example, network analysis, route mapping, and scheduling. For studying and addressing graph problems, graph search techniques such as breadth-first search are helpful. BFS (breadth-first search) is a famous graph search technique that can be used to solve various problems, including finding the shortest path in a graph and solving puzzle games like Rubik's Cubes.

This blog will discuss one such problem, Minimum Operations to Convert Number, and solve it using BFS.

Problem Statement

You are given two integers, START and GOAL. You are also given a 0-indexed integer array NUMS with distinct integers. 

If initially, an integer, X = START, and 0 <= X <= 1000, you can perform the following operations, for any index i in the array:

  • X + NUMS[i] = A
  • X - NUMS[i] = B
  • X ^ NUMS[i] = C


Also, each NUMS[i] can be used in any order and any number of times.

The problem asks you to find the minimum number of operations to convert START into GOAL,  and if this is not possible, return -1.

Let us try to understand this with the help of a few examples.

Example

  •      START = 2

GOAL = 12

NUMS = [2, 4, 12]

2 + 12 = 14

     14 - 2 = 12

So, minimum number of operations performed =

  •      START = 0

GOAL = 3

NUMS = [1]

0 + 1 = 1

     1 + 1 = 2

     2 + 1 = 3

So, minimum number of operations performed = 3

  •      START = 0

GOAL = 1

NUMS = [2, 8, 16]

There’s no way to convert 0 to 1.

So, the answer is = -1 

Approach

We will be using BFS to solve this problem. Our goal is to reach GOAL from START, and we are allowed to perform three types of operations.

Let’s suppose we use these operations on start and we get:

START + NUMS[i] = A

START - NUMS[i] = B

START ^ NUMS[i] = C

  • Either A, B, or C is equal to GOAL.
  • None of A, B, or C is equal, and we need to perform these operations until we reach GOAL. But this could result in a Time Limit Exceed, so to avoid this, we would maintain an array VISITED, which would keep a record of the values that have been calculated before. In this way, we would not have to perform repetitive calculations. 
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

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;
}

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

 

Previous article
DSatur Algorithm for Graph Coloring
Next article
Check if a Given Graph is Strongly Connected ( Kosaraju's BFS )🥷🏻
Live masterclass