Smallest Lock Code

Medium

A combination lock shows a string of digits digits of even length. You may apply two moves any number of times, in any order: - **Add:** add step to every digit at an odd position (0-indexed); digits wrap around from 9 back to 0. For example, with step = 5, 3456 becomes 3951. - **Rotate:** rotate the string to the right by shift positions. For example, with shift = 1, 3456 becomes 6345. Return the lexicographically smallest string you can reach with these moves (the original string counts, if you do nothing).

Example 1

digits="1938", step=1, shift=2 → '1039'

Rotating by 2 only gives 1938 and 3819, and odd positions 1 and 3 turn together. For 1938, adding 1 once gives 1039; every variant of 3819 starts with 3, which is worse. The answer is 1039.

Example 2

digits="95", step=5, shift=1 → '04'

95 → add: 90 → rotate: 09 → add: 04. Nothing smaller is reachable: the first digit is always 0 or 5, the second always 4 or 9.

Example 3

digits="000000", step=3, shift=4 → '000000'

Constraints

2 ≤ len(digits) ≤ 100
len(digits) is even
digits consists of digits 0 to 9
1 ≤ step ≤ 9
1 ≤ shift ≤ len(digits) − 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search String Enumeration