Minimum multiplications to reach end

Pre Requisite: Shortest path in undirected graph with unit weights

Intuition:

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 the 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 posssible, return -1.

Dry Run:

Solution:

#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 */
        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;
}
import java.util.*;

class Solution {

    /* Function to determine minimum 
    multiplications to reach end */
    public int minimumMultiplications(int[] arr, 
                            int start, int end) {
        
        // Base case
        if (start == end) return 0;
        
        // Size of array
        int n = arr.length;
        int mod = 100000; // mod
        
        /* Array to store minimum 
        steps (distance array) */
        int[] minSteps = new int[mod];
        Arrays.fill(minSteps, Integer.MAX_VALUE);
        
        /* Queue to implement 
        Dijkstra's algorithm */
        Queue<int[]> q = new LinkedList<>();
        
        // Mark initial position as 0
        minSteps[start] = 0;
        
        // Add the initial node to queue
        q.add(new int[]{0, start});
        
        // Until the queue is empty
        while (!q.isEmpty()) {
            
            // Get the element
            int[] p = q.poll();
            
            int steps = p[0]; // steps 
            int val = p[1]; // 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.add(new int[]{steps + 1, num});
                }
            }
        }
        
        /* Return -1 if reaching 
        end is not possible */
        return -1;
    }

    public static void main(String[] args) {
        int start = 3, end = 30;
        int[] arr = {2, 5, 7};
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution();
        
        /* Function call to determine minimum 
        multiplications to reach end */
        int ans = sol.minimumMultiplications(arr, start, end);
        
        // Output
        System.out.println("The minimum multiplications to reach end is: " + ans);
    }
}
from collections import deque

class Solution:
    
    # Function to determine minimum 
    # multiplications to reach end 
    def minimumMultiplications(self, arr, start, end):
        
        # Base case
        if start == end:
            return 0
        
        # Size of array
        n = len(arr)
        mod = 100000 # mod
        
        # Array to store minimum 
        # steps (distance array)
        minSteps = [float('inf')] * 100000
        
        # Queue to implement 
        # Dijkstra's algorithm
        q = deque()
        
        # Mark initial position as 0
        minSteps[start] = 0
        
        # Add the initial node to queue
        q.append((0, start))
        
        # Until the queue is empty
        while q:
            
            # Get the element
            steps, val = q.popleft()
            
            # Check for adjacent neighbors
            for i in range(n):
                
                # Value of neighboring node
                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.append((steps + 1, num))
        
        # Return -1 if reaching 
        # end is not possible
        return -1

if __name__ == "__main__":
    start = 3
    end = 30
    arr = [2, 5, 7]
    
    # Creating an instance of 
    # Solution class
    sol = Solution()
    
    # Function call to determine minimum 
    # multiplications to reach end
    ans = sol.minimumMultiplications(arr, start, end)
    
    # Output
    print("The minimum multiplications to reach end is:", ans)
class Solution {
    
    /* Function to determine minimum 
    multiplications to reach end */
    minimumMultiplications(arr, start, end) {
        
        // Base case
        if (start === end) return 0;
        
        // Size of array
        let n = arr.length;
        let mod = 100000; // mod
        
        /* Array to store minimum 
        steps (distance array) */
        let minSteps = new Array(100000).fill(Number.MAX_SAFE_INTEGER);
        
        /* Queue to implement 
        Dijkstra's algorithm */
        let 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.length > 0) {
            
            // Get the element
            let [steps, val] = q.shift();
            
            // Check for adjacent neighbors
            for (let i = 0; i < n; i++) {
                
                // Value of neighboring node
                let 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;
    }
}

let start = 3, end = 30;
let arr = [2, 5, 7];

/* Creating an instance of 
Solution class */
let sol = new Solution();

/* Function call to determine minimum 
multiplications to reach end */
let ans = sol.minimumMultiplications(arr, start, end);

// Output
console.log("The minimum multiplications to reach end is:", ans);

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.

Problem List

Minimum multiplications to reach end

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

How to identify this as a problem on Graphs?

How to identify the neighbors for a node?

Edge Cases:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code