Minimum Multiplications to reach End

Intuition

Each number from 0 to 999 can be treated as a graph node because every multiplication is taken modulo 1000. From a current node x, multiplying by any arr[i] leads to exactly one next node, so the problem becomes finding the shortest path in an unweighted graph. BFS is the right tool because every edge costs one multiplication.

Algorithm

1Handle the easy case first: if start == end, return 0.
2Create a distance array of size 1000 (or 1001 in this implementation) and initialise all values to infinity.
3Set distance[start] = 0 and push start into a queue.
4While the queue is not empty:
5 Pop the front value curr.
6 For every multiplier val in arr, compute next = (curr * val) % 1000.
7 If distance[curr] + 1 improves distance[next], update it and enqueue next.
8 If next == end, return distance[next] immediately because BFS found the shortest path.
9If BFS finishes without reaching end, return -1.

Example Walkthrough

Input: arr = [2, 5, 7], start = 3, end = 30

1.Start at 3 with distance 0.
2.From 3, one move gives 6, 15, and 21.
3.From 6, multiplying by 5 gives 30.
4.We reached 30 in 2 multiplications: 3 -> 6 -> 30.

Output: 2

Common Pitfalls

•The graph is over modulo values, not over indices of the array.
•Without the distance/visited check, the queue can revisit the same remainder many times and blow up work.
•Returning as soon as end is first discovered is valid only because BFS processes states in increasing distance order.

Minimum Multiplications to reach End.java

Java


import java.util.*;

// Approach: BFS over the 1000 possible values modulo 1000.
// From a value x, every arr[i] creates a directed edge to (x * arr[i]) % 1000.
// BFS guarantees the first time we reach end, we used the minimum number of multiplications.
// Time: O(1000 * arr.length) Space: O(1000)

class Solution {

    public int minSteps(int[] arr, int start, int end) {
        // Edge Case
        if (start == end) {
            return 0;
        }

        // Mod is 1000, so 1000 values at max
        int[] steps = new int[1001];
        Arrays.fill(steps, 1000000000);
        Deque<Integer> q = new ArrayDeque<>();

        steps[start] = 0;
        q.offerLast(start);

        while (!q.isEmpty()) {
            int curr = q.removeFirst();

            // Like recursion, multiplying with every element
            for (int val : arr) {
                int next = (curr * val) % 1000;

                // Same as min step in recursion, step + 1 because the step is valid or not
                if (steps[curr] + 1 < steps[next]) {
                    steps[next] = steps[curr] + 1;

                    if (next == end) {
                        return steps[next];
                    }

                    q.offerLast(next);
                }
            }
        }

        return -1;
    }
}

Was this solution helpful?