Minimum Multiplications to reach End | BFS Solution in Python

Solve Minimum Multiplications to reach End with a clean BFS, modular math, and commented Python code. Easy steps, dry run, and Big-O explained.

Here’s the [Problem Link] to begin with.

1. What does the problem ask?

You have:

• an array arr of positive integers (the “multipliers”),
• a start number and a target end,
• a fixed mod value = 100000 (so every multiplication is taken mod 100000).

At each move you may pick any multiplier m in arr and change your current
number x to

(x × m) mod 100000

Return the minimum number of moves needed to reach end from start.
If it is impossible, return -1.

2. Example

3. Intuition & approach

3.1 Why Breadth-First Search?

• Each move costs exactly one step.
• We want the fewest steps, so BFS—which explores level by level—naturally gives the shortest path in an unweighted graph.

3.2 Graph model

• Vertices: all numbers 0 … 99999.
• Edge: from x to (x × m) mod 100000 for every m in arr.

Our job is the shortest path from the vertex start to the vertex end.

3.3 Distance array

A 1-D list distance[num] stores the smallest steps discovered so far.
Start with ∞, except distance[start] = 0.
We push (steps, num) into a queue and update neighbours only when
we find a better (smaller) step count.

4. Python code

from typing import List
import sys
from collections import deque


class Solution:
    def minimumMultiplications(self, arr: List[int], start: int, end: int) -> int:
        MOD = 100000                        # fixed modulus
        distance = [sys.maxsize] * MOD
        distance[start] = 0                 # 0 moves to reach start

        queue = deque()
        queue.append([0, start])            # [steps_so_far, current_num]

        while queue:
            step, num = queue.popleft()

            if num == end:                  # reached goal
                return step

            # try every multiplier
            for m in arr:
                new_num  = (num * m) % MOD
                new_step = step + 1

                # relax only if shorter path
                if new_step < distance[new_num]:
                    distance[new_num] = new_step
                    queue.append([new_step, new_num])

        return -1                           # unreachable

5. Step-by-step explanation

1. Distance table – size = 100 000, keeps smallest steps to each residue.
2. Queue – classic BFS; stores pairs of (steps, number).
3. Loop
   • Pop the earliest state.
   • If number equals end, we are done (BFS guarantee).
   • Otherwise, multiply it by every m in arr, take mod 100000, and push the neighbour if we just found a quicker route.
4. End – if the queue empties without seeing end, no sequence of allowed multiplications can reach it → return -1.

6. Dry run

arr = [2, 5], start = 3, end = 30

Shortest sequence: 3 → 15 → 30.

7. Complexity

With the modulus fixed at 100 000, this is perfectly fine for interview-size inputs.

8. Conclusion

• The task “Minimum Multiplications to reach End” is a textbook case for BFS in a modular state space.
• Store steps in a distance array, multiply & mod to produce neighbours, and stop as soon as you pop the target.
• The solution runs fast (linear in the state space) and uses only simple data structures—ideal for coding interviews or contests.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.