DAY 43 - Minimum Multiplications to reach End

Hey everyone! Welcome back to another day of problem-solving. It's day 43, and I can't believe I have been on this for more than 40 days. Never Have I ever committed to upskilling myself so much. Today, we will be doing another graph problem which eventually we will solve using Dijkstra's algorithm. So if you have no clue what we are doing it I suggest reading the previous article on Day 40.

Question: Minimum Multiplications to reach End

Given start, end and an array arr of n numbers. At each step, start is multiplied with any number in the array and then mod operation with 100000 is done to get the new start.

Your task is to find the minimum steps in which end can be achieved starting from start. If it is not possible to reach end, then return -1.

Example 1:

• Input:
• arr[] = {3, 4, 65}
• start = 7, end = 66175
• Output:
• 4
• Explanation:
• Step 1: 7*3 = 21 % 100000 = 21
• Step 2: 21*3 = 63 % 100000 = 63
• Step 3: 63*65 = 4095 % 100000 = 4095
• Step 4: 4095*65 = 266175 % 100000 = 66175

Example 2:

• Input:
• arr[] = {2, 5, 7}
• start = 3, end = 30
• Output:
• 2
• Explanation:
• Step 1: 3*2 = 6 % 100000 = 6
• Step 2: 6*5 = 30 % 100000 = 30

Constraints:

1 <= n and n <= 10^4
1 <= arr[i] and arr[i] <= 10^4
1 <= start, end < 10^5

Intuition:

• So we know the start and end here.
• Although this does not form a graph it does use the bfs algorithm.
• It's better if I show you guys with an example.
• Say for example 2:
• We start with 3, the options we can multiply it with are 2 , 5 & 7. So we do that and we store our result and our multiplication count.
• Now We do that for all the 3 numbers produced.
• If at some point we reach our end in any of these new numbers formed , we know this is the least because any further we go we will only be adding to the the multiplications. So let's try to write the algorithm and understand it.

Algorithm:

1. Initialize a queue (q) to store pairs of numbers (node) and the number of steps taken to reach that number (steps).
2. Enqueue the starting number (start) with 0 steps.
3. If the start number is already equal to the end number, return 0, as no multiplications are needed.
4. Create a distance array (dist) to store the minimum number of multiplications required to reach each number from the start number. Initialize all values in the dist array to a large value (1e9), except for the start number, which is set to 0.
5. Set the modulo value (mod) to 100000.
6. Perform a breadth-first search (BFS) using the queue:
7. Dequeue a pair (node, steps) from the front of the queue.
8. Iterate over each number (it) in the array (arr).
9. Calculate the next number (num) by multiplying the current number (it) with the dequeued node, modulo the mod value.
10. If the number of steps taken to reach num is less than the previously recorded steps in the dist array, update the dist array with the new minimum number of steps.
11. If num is equal to the end number, return the calculated steps, as we have reached the desired number.
12. Enqueue the new number (num) with steps + 1 to continue the BFS.
13. If the end number is unattainable, return -1.

Code:

int mod = 100000;
    int minimumMultiplications(vector<int>& arr, int start, int end) {
        queue<pair<int, int>> q;
        q.push({start, 0});
        if(start == end) return 0;
        vector<int> dist(100000, 1e9);
        dist[start] = 0;
        while (!q.empty())
        {
            int node = q.front().first;
            int steps = q.front().second;
            q.pop();

            for (auto it : arr)
            {
                int num = (it * node) % mod;
                if (steps + 1 < dist[num])
                {
                    dist[num] = steps + 1;

                    if (num == end)
                        return steps + 1;
                    q.push({num, steps + 1});
                }
            }
        }
        return -1;
    }

Complexity Analysis:

• Time: O(10^5)
• Space: O(10^5)