Minimum Multiplications to Reach End

Given an array arr of multipliers, a start number, and an end number, in each step you may replace the current number cur by (cur * arr[i]) % 100000 for any i. Return the minimum number of steps to transform start into end, or -1 if it's impossible.

Hints

· Stuck? Reveal one nudge at a time.

Because of the % 100000, only 100000 values are possible — a finite graph.

Multiplying by an arr value is a single step (unit-weight edge).

BFS from start gives the minimum number of multiplications to reach end.

Common doubts

Every edge costs exactly one step, so BFS already visits states in step order; Dijkstra's heap adds a log factor for no benefit.

The modulus caps the reachable values at 100000, so BFS terminates even though multiplication is unbounded in principle.

When end lies in no residue reachable from start via the given multipliers.

Interview follow-ups

· What an interviewer asks next.

Same BFS; the state-space size is just the new modulus.

Then it's a weighted shortest path — use Dijkstra with actual weights.

Fun facts

This is a classic 'implicit graph' problem — the graph is defined by a rule, not an edge list.
The same modular-state BFS solves lock-combination and number-transformation puzzles.

Asked at

AmazonGoogle

Frequently Sometimes Occasionally

Example 1

Input: arr = [2, 5, 7], start = 3, end = 30
Output: 2
3 → 6 (×2) → 30 (×5).

Example 2

Input: arr = [2], start = 1, end = 3
Output: -1
Powers of two never reach 3.

Constraints

- 1 <= arr.length <= 10^4 - 1 <= arr[i] < 100000 - 0 <= start, end < 100000

Every reachable value lives in 0 .. 99999 (because of the % 100000), so this is a graph on 100000 states: from state cur, one step (an edge of weight 1) leads to (cur * arr[i]) % 100000 for each multiplier. "Minimum steps" is then the shortest path from start to end on an unweighted graph — a job for BFS.

BFS from start, generating each state's up-to-|arr| successors and recording the step count when first reached; the first time you pop end, that count is the answer. Since edges are unit-weight, plain BFS is optimal; Dijkstra also works but its heap is unnecessary overhead. O(100000 · |arr|).

Prerequisites

Before you start

· Concepts used directly in the solution.

State-space graph. nodes are the 100000 residues.

BFS on unit weights. first-reach step count is the shortest.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“How large is the state space?”

100000 — every value is taken mod 100000.

“If end is unreachable?”

Return -1.

The ideal opening — say it like this

Each number mod 100000 is a node; multiplying by an arr value is a unit-weight edge, so I BFS from start.

The step count when I first reach end is the minimum; if BFS never reaches it, return -1.

Understand the problem

Worked example — arr = [2, 5, 7], start = 3, end = 30

3 --*2--> 6 --*5--> 30   (2 steps)
answer = 2

Key observations

1Aha

Mod bounds the state space

Only 100000 possible values.

2Aha

Each multiplication is a unit edge

So BFS gives the fewest steps.

3Aha

First reach is optimal

BFS settles states in step order.

Brute force vs optimal

	Dijkstra	BFS
Structure	min-heap by steps	plain queue
Time	O(S·\|arr\|·log S)	O(S·\|arr\|)
Note	heap is unnecessary	optimal for unit weights

Both return the same minimum step count; BFS is the natural fit. Full code is in the Approaches selector below.

Summary

Key takeaway

The % 100000 makes a finite 100000-state graph; multiplying is a unit-weight edge. BFS from start gives the minimum steps to end, or -1. O(100000·|arr|).

BFS from start; neighbour = (cur * m) % 100000; first reach of end = answer