Fewest Spins to Open the Combination Lock
Implement minSteps
A 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.
Example 1:
Input: keys = [3,4,7], start = 5, end = 135
Output: 3
Example 2:
Input: keys = [2], start = 3, end = 3
Output: 0
Example 3:
Input: keys = [10], start = 1, end = 7
Output: -1
+ 17 hidden test cases run on Submit.
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
keys =
[3, 4, 7]
start =
5
end =
135