Special Keyboard

Moving the left finger left to the middle and then from the middle to the left repeatedly might look optimal, but it is not. Particularly for cases where $n\%4==0$.

For example in this case:

1
4 3

The answer should be 3.

Let’s try to find the costliest cycles. By cycle we mean after doing some operations all fingers will be at their original position.

There is no cycle of length 1, and the costliest 1-length of typing would be moving the left finger to the middle.

The costliest 2-length cycle would be moving the left finger to the middle and taking it back to the leftmost key.

The costliest 3-length cycle would be moving the left finger to the middle and moving it from the middle to the 3/4 ‘th key and after that back to the leftmost key.

The costliest 4-length typing will be between doing the 2-length cycle twice.

And so on…

As you can see, all cycles of length $\leq2$ consist of some 2-length cycles and some 3-length cycles.

We need to find out which cycle gives us the most time per character typed ratio and do that until we reach $m$.

After calculating costs for 2, and 3-length cycles, the whole problem can be formulated in $O(1)$.

Time Complexity: $O(1)$

Space Complexity: $O(1)$