Minimum Rotations for Circular Lock

Minimum Rotations for Circular Lock is a clean greedy warm-up. It teaches a habit that solves a surprising number of problems: when the pieces don't interact, optimize each one on its own.

The slow way first

You might imagine searching over combinations of moves: spin this wheel, then that one, exploring sequences until the codes match. That is a huge, pointless search space.

The question to ask: do the wheels affect each other? They do not. Spinning wheel 0 never changes wheel 1. So the total is just the sum of the cost of each wheel, and we can solve each wheel by itself.

The idea: cheapest spin per wheel

For one wheel going from a to b, there are two ways around the ring. The direct distance is d = |a - b|. The wrap-around distance is 10 - d (go the other way and loop past 0/9). The cost of that wheel is the smaller one: min(d, 10 - d). Sum it over all wheels.

Because the wheels are independent, the local best choice on each wheel is also the global best. That is exactly what makes a greedy choice valid here.

Walk through it

Step through the animation. The wheel pointer moves left to right. For each wheel we show min(d, 10 - d) underneath, then add it to the running total. Wheel 1 is already 5 → 5, so it costs 0. Wheel 3 goes 8 → 1: direct is 7, but wrapping the other way is 10 - 7 = 3, so we take 3.

Pseudocode

total = 0
for each wheel, with current digit a and target digit b:
    d = |a - b|                 # direct distance
    wrap = 10 - d               # the other way around the ring
    cost = min(d, wrap)         # cheaper direction
    total = total + cost
return total

The Python solution

def min_rotations(start, target):
    total = 0
    for a, b in zip(start, target):
        d = abs(a - b)
        wrap = 10 - d
        cost = min(d, wrap)
        total += cost
    return total

• total accumulates the rotations across all wheels.
• zip(start, target) pairs each current digit a with its target digit b.
• d = abs(a - b) is the direct distance ignoring the wrap.
• wrap = 10 - d is the distance going the other way around the 10-digit ring.
• cost = min(d, wrap) picks the shorter direction — the greedy choice for this wheel.
• We add each wheel's cost and return the running total.

Complexity

We touch each wheel once and do constant work, so the whole thing is O(n) time with no extra storage beyond a counter.

When this pattern shows up

Practice