☕ DSA Java Articles

Topics › Graphs › Shortest Path Algorithms and Problems

Minimum multiplications to reach end

Hard TUF ID 523 A2Z

Java source ↗ Edit this article ↗

Problem

You are given an array arr of multipliers and two numbers start and end. In one step you may pick any arr[i] and replace start with (start * arr[i]) % 100000. Return the minimum number of steps needed to turn start into end, or -1 if it is impossible. Multipliers can be reused any number of times.

Constraints (GeeksforGeeks): 1 ≤ arr.length ≤ 10^4, 1 ≤ arr[i] ≤ 10^5, 1 ≤ start, end < 10^5.

Example 1

arr = [2, 5, 7], start = 3, end = 30
answer = 2          // 3 * 2 = 6, then 6 * 5 = 30

Example 2

arr = [3, 4, 65], start = 7, end = 66175
answer = 4          // 7 -> 21 -> 63 -> 4095 -> 266175 % 100000 = 66175

At first sight this looks like a number puzzle, but the modulo makes it a graph problem. Every value is one of the residues 0 to 99999, so there are exactly 100000 possible states. From a state x there is an edge to (x * m) % 100000 for every multiplier m. Each step costs one, so the question is the length of the shortest path from start to end in that implicit graph. We never build the graph: the neighbours of x are computed on the fly.

Approach 1: Dijkstra on the residues

Intuition. This sits in the shortest-path section of the sheet, and the most general tool is Dijkstra: keep dist[x], the fewest steps known to reach residue x, and repeatedly expand the unexpanded residue with the smallest dist from a min-heap. When end comes out of the heap, its distance is final, because every other entry in the heap is at least as far away and steps are never negative.

Two details matter. First, x * m can be as large as about 10^5 × 10^5 = 10^10, which overflows a 32-bit int, so the product is computed in long before the modulo. Second, the state space is bounded at 100000, so the search always terminates: if the heap empties without reaching end, the answer is -1.

Algorithm.

  1. dist[start] = 0, everything else infinity; push {0, start}.
  2. Pop the entry with the fewest steps. If its value is end, return its steps. If it is stale, skip it.
  3. For each multiplier m, compute next = value * m % 100000. If steps + 1 < dist[next], update it and push {steps + 1, next}.
  4. Return -1 when the heap is empty.
static int dijkstra(int[] arr, int start, int end) {
    int[] dist = new int[MOD];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    pq.offer(new int[]{0, start});                   // {steps, value}
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int steps = cur[0], value = cur[1];
        if (value == end) return steps;              // first time end leaves the heap, its distance is final
        if (steps > dist[value]) continue;           // stale entry
        for (int m : arr) {
            int next = (int) ((long) value * m % MOD);   // long: value * m can reach about 10^10
            if (steps + 1 < dist[next]) {
                dist[next] = steps + 1;
                pq.offer(new int[]{steps + 1, next});
            }
        }
    }
    return -1;
}

Complexity. Each of the 100000 residues is expanded at most once, and each expansion tries all m multipliers, so there are at most 100000 · m relaxations. Each costs a heap operation, giving O(100000 · m · log(100000 · m)) time in the worst case. Space O(100000) for dist, plus the heap.

That works, but the heap is doing a job nobody asked for. Every edge has the same weight.

Approach 2: Optimal, plain BFS

Intuition. When all edges cost exactly one, a FIFO queue already pops states in non-decreasing order of steps. Everything at distance d enters the queue before anything at distance d + 1, because a state at distance d + 1 can only be discovered while expanding a state at distance d. So the queue does what the heap did, without the logarithm. This is the “Dijkstra with a queue” form Striver uses for this problem.

With BFS, the first time a residue is discovered is already its shortest distance. So instead of comparing steps + 1 < dist[next] we only need “has next been seen?”, and we can return the moment end is discovered rather than when it is popped.

Algorithm.

  1. If start == end, return 0.
  2. dist[start] = 0, every other entry -1 (unseen); enqueue start.
  3. Dequeue value. For every multiplier m: next = value * m % 100000. If next is unseen, set dist[next] = dist[value] + 1; return it if next == end; otherwise enqueue it.
  4. Return -1 when the queue is empty.
static int bfs(int[] arr, int start, int end) {
    if (start == end) return 0;
    int[] dist = new int[MOD];
    Arrays.fill(dist, -1);                           // -1 = not reached yet
    dist[start] = 0;
    Deque<Integer> queue = new ArrayDeque<>();
    queue.offer(start);
    while (!queue.isEmpty()) {
        int value = queue.poll();
        for (int m : arr) {
            int next = (int) ((long) value * m % MOD);
            if (dist[next] == -1) {
                dist[next] = dist[value] + 1;
                if (next == end) return dist[next];  // the first discovery is the shortest
                queue.offer(next);
            }
        }
    }
    return -1;
}

Dry run on Example 1 (arr = [2, 5, 7], start = 3, end = 30):

dequeued dist new residues discovered
3 0 6, 15, 21 (distance 1)
6 1 12, 30 (distance 2): 30 is the end, return 2

6 * 7 = 42 is never reached because we return as soon as 30 appears.

Complexity. Time O(100000 · m): each residue is enqueued at most once and tries every multiplier. Space O(100000) for dist and the queue. The bound depends on the modulus, not on how large the numbers would get without it, which is the whole point of seeing it as a graph.

Why a bounded state space guarantees termination

Without the modulo, repeated multiplication would produce ever larger numbers and a search could run forever. With it, there are only 100000 distinct values, and each one is processed at most once, so both searches stop. This also explains the -1 cases. With arr = [2] and start = 1, every reachable value after the first step is even, so an odd end such as 3 is never discovered; the queue drains after visiting the 2505 distinct powers of two modulo 100000, and we return -1.

The same pattern appears in many puzzles: “lock combinations”, “minimum operations to turn one number into another”, “word ladder”. Whenever the values that can appear form a finite, small set and every move costs the same, model values as nodes and moves as edges, then run BFS.

Edge cases and pitfalls