Problem Statement

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

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

Examples

Example 1:

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
Therefore, in minimum 2 multiplications, we reach the end number which is treated as a destination node of a graph here.

Example 2:

Input: arr = [3, 4, 65], start = 7, end = 66175
Output: 4

Explanation:
Step 1: 7*3 = 21 % 100000 = 21
Step 2: 31*3 = 63 % 100000 = 63
Step 3: 63 * 65 = 4095 % 100000 = 4095
Step 4: 4095 * 65 = 266175 % 100000 = 66175
Therefore, in minimum 4 multiplications we reach the end number which is treated as a destination node of a graph here.

Different Approaches

1️⃣ Modified Dijkstra Approach

How to Identify this as a Problem on Graphs?

When dealing with problems that involve transforming one value to another through a series of operations, it's helpful to think of the problem as a graph because:

• Node Representation: Each possible value of start can be considered a node (or start) in a graph.
• Transitions as Edges: The operations (multiplying by any number in the array and taking modulo 100000) represent transitions (or edges) between these states.
• Path Finding: The goal is to find the shortest sequence of operations (steps) that transform start into end. This is analogous to finding the shortest path between two nodes in a graph.

Once it is clear, this problem boils down to finding Shortest path in undirected graph with unit weights.

How to Identify the neighbors for a node ?

For any current node (value), its neighbors are nodes (values) obtained by multiplying it by each number in the array arr and then taking modulo 100000.

Edge Cases:

• If the start and end are identical, there is no transition (steps) required. Hence, 0 can be returned.
• If it is not possible to transform start to end, return -1.

Approach:

• Create a array to store minimum steps to reach a node initialized to infinity for all possible values. Set the distance of the starting value (start) to 0. Use a queue to perform BFS.
• Perform BFS traversal starting from the source node (start value).
• For each node (value), update the distance of its adjacent nodes (values) if a shorter path is found and push the node in the queue. Return the steps taken if end value is reached.
• If reaching end value is not possible, return -1.

Dry Run:

Code:

#include <bits/stdc++.h>
using namespace std;

/* Define P as a shorthand for
the pair <int,int> type */
#define P pair <int,int>

class Solution {
public:

    /* Function to determine minimum 
    multiplications to reach end */
    int minimumMultiplications(vector<int>& arr, 
                            int start, int end) {
                                
        // Base case
        if(start == end) return 0;
        
        // Size of array
        int n = arr.size();
        int mod = 100000; // mod
        
        /* Array to store minimum 
        steps (distance array) */
        vector<int> minSteps(1e5, INT_MAX);
        
        /* Queue to implement 
        Dijkstra's algorithm */
        // first = steps
        // second = value
        queue <P> q;
        
        // Mark initial position as 0
        minSteps[start] = 0;
        
        // Add the initial node to queue
        q.push({0, start});
        
        // Until the queue is empty
        while(!q.empty()) {
            
            // Get the element
            auto p = q.front(); 
            q.pop();
            
            int steps = p.first; // steps 
            int val = p.second; // value
            
            // Check for adjacent neighbors
            for(int i=0; i < n; i++) {
                
                // Value of neighboring node
                int num = (val * arr[i]) % mod;
                
                // If end is reached, return steps taken
                if(num == end) return steps+1;
                
                /* Check if the current steps taken is 
                less than earlier known steps */
                if(steps+1 < minSteps[num]) {
                    
                    // Update the known steps
                    minSteps[num] = steps+1;
                    
                    // Insert the pair in queue
                    q.push({steps+1, num});
                }
            }
        }
        
        /* Return -1 if reaching 
        end is not possible */
        return -1;
    }
};

int main() {
    int start = 3, end = 30;
    vector<int> arr = {2, 5, 7};
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to determine minimum 
    multiplications to reach end */
    int ans = sol.minimumMultiplications(arr, start, end);
    
    // Output
    cout << "The minimum multiplications to reach end is: " << ans;
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O(100000*N) (where N is the length of given array)
  • A simple BFS traversal is performed taking O(V+E) time, where V represents nodes (which can be 100000 in the worst case) and E represents the number of edges (transitions) (which can be 100000*N, since for every value, N edges are formed). This makes the overall time complexity as O(100000*N).
• Space Complexity: O(100000*N)
  • Queue space will store all the transitions possible in worst-case resulting in O(100000*N) space.
    The array to store minimum steps takes O(100000) space.