PPractick

The problem

A lock has a 5-digit display showing a number (start). Each press of button i multiplies the current value by arr[i] and keeps the result modulo 100000. What's the fewest presses to make the display show end? Return −1 if it's impossible. There are only 100,000 possible values, so treat each value as a graph node, with an edge for each button. The fewest presses is then a BFS shortest path from start to end.

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

Function signature

int minimumMultiplications(const vector<int>& arr, int start, int end);  // values mod 100000

Test cases

Input (arr, start, end)	Output	Explanation
([2, 5, 7], 3, 30)	2	3 → 6 → 30
([3, 4, 65], 7, 66175)	4	7 → 21 → 63 → 4095 → 266175 mod 100000
([2, 3], 1, 12)	3	No 2-press product equals 12
([10], 5, 7)	-1	Multiples of 10 never end in 7
([2], 1, 1)	0	Already there

(Confirm: all arithmetic is modulo 100000; 0 ≤ start, end < 100000; buttons can be pressed any number of times.)

How interviewers phrase it

• "Given start, end and an array of multipliers, find the minimum steps to reach end where each step multiplies by an array element modulo 100000" (GeeksforGeeks "Minimum Multiplications to reach End").

Clarifying questions to ask

1. Is the modulus fixed at 100000? (Yes.)
2. Can the same multiplier be used repeatedly? (Yes.)
3. What if start already equals end? (0 steps.)

Follow-ups to expect

1. "Why is this a graph problem?"
2. "Why BFS rather than Dijkstra?"
3. "Why does the search terminate?"
4. "What's the worst-case work?"
5. "Complexity?"

Related questions

• Cycle Detection in Undirected Graph (bfs) Hard
• Word ladder I Hard
• Word ladder II Hard
• Topological sort or Kahn's algorithm Hard
• Alien Dictionary Hard
• Shortest path in undirected graph with unit weights Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in