Fewest Spins to Open the Combination Lock
Solve this ProblemA combination lock shows a number from 0 to 999. You own a few keys; using key k on a lock showing s changes it to (s × k) mod 1000, and every use costs one spin. Find the fewest spins that turn the start number into the target number, or -1 if that is impossible.
There is no graph in the input: the numbers are the nodes and each key defines a road out of every number. Because every road costs one spin, a breadth-first search over the numbers finds the answer.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ keys.length ≤ 5; 2 ≤ keys[i] ≤ 999; 0 ≤ start, end ≤ 999 - ◆
The lock shows a number from 0 to 999. One spin picks any key k and changes the shown number s to (s × k) mod 1000 - ◆
Every spin costs 1; you may use the same key several times - ◆
Return the fewest spins needed to turn start into end (0 when they are equal), or -1 if it is impossible
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Keep Relaxing Spin Counts Until Nothing Improves
BruteThere are only M = 1000 possible numbers, so keep one entry per number: the fewest spins found so far (infinity at the start, 0 for the start number). Sweep over all numbers again and again: from a number with a known count, applying each key gives another number that can be reached with one more spin, so lower its count if that is better. Stop when a whole sweep changes nothing. Each sweep costs M · K and the number of sweeps grows with the route length.
O(M · K · steps)O(M)1class Solution {
2 public int minSteps(int[] keys, int start, int end) {
3 int MOD = 1000;
4 int INF = Integer.MAX_VALUE;
5 int[] dist = new int[MOD];
6 Arrays.fill(dist, INF);
7 dist[start] = 0;
8 boolean changed = true;
9 while (changed) {
10 changed = false;
11 for (int s = 0; s < MOD; s++) {
12 if (dist[s] == INF) continue;
13 for (int k : keys) {
14 int next = (s * k) % MOD;
15 if (dist[s] + 1 < dist[next]) {
16 dist[next] = dist[s] + 1;
17 changed = true;
18 }
19 }
20 }
21 }
22 return dist[end] == INF ? -1 : dist[end];
23 }
24}Optimal — Breadth-First Search Over the Numbers
OptimalTreat every number 0 … 999 as a node and every key as a road from s to (s × k) mod 1000. All roads cost one spin, so a breadth-first search from the start finds the fewest spins: the first time the target is taken from the queue, its distance is the answer. Each number is queued at most once and tried with K keys: O(M · K). If the queue empties, the target cannot be reached.
O(M · K)O(M)1class Solution {
2 public int minSteps(int[] keys, int start, int end) {
3 int MOD = 1000;
4 int[] dist = new int[MOD];
5 Arrays.fill(dist, -1);
6 dist[start] = 0;
7 Deque<Integer> queue = new ArrayDeque<>();
8 queue.add(start);
9 while (!queue.isEmpty()) {
10 int s = queue.poll();
11 if (s == end) return dist[s];
12 for (int k : keys) {
13 int next = (s * k) % MOD;
14 if (dist[next] == -1) {
15 dist[next] = dist[s] + 1;
16 queue.add(next);
17 }
18 }
19 }
20 return -1;
21 }
22}