Skip to content

4070. Minimum Rotations to Dial a Number I

SourceWeekly Contest 522 Q1DifficultyEasyRating1156

Description

You are given a string s of length 10 consisting of digits.

The dial contains the digits 0 through 9 in order and is circular, so 0 and 9 are adjacent. The pointer initially points to 0.

To dial each digit of s in order, rotate the pointer until it points to that digit. Each rotation moves the pointer to an adjacent digit, and you may rotate in either direction. Dialing a digit that the pointer already points to requires no rotations.

Return the minimum total number of rotations needed to dial every digit of s.

 

Example 1:

Input: s = "0192837465"

Output: 25

Explanation:

Step From To Rotations
1 0 0 0
2 0 1 1
3 1 9 2
4 9 2 3
5 2 8 4
6 8 3 5
7 3 7 4
8 7 4 3
9 4 6 2
10 6 5 1

The total is 0 + 1 + 2 + 3 + 4 + 5 + 4 + 3 + 2 + 1 = 25, which is the minimum total number of rotations.

Example 2:

Input: s = "1200210200"

Output: 12

Explanation:

Step From To Rotations
1 0 1 1
2 1 2 1
3 2 0 2
4 0 0 0
5 0 2 2
6 2 1 1
7 1 0 1
8 0 2 2
9 2 0 2
10 0 0 0

The total is 1 + 1 + 2 + 0 + 2 + 1 + 1 + 2 + 2 + 0 = 12, which is the minimum total number of rotations.

 

Constraints:

  • s.length == 10
  • s consists only of digits '0' to '9'

Solutions

Solution 1

Thinking

Each step only depends on the current pointer position and the next digit to dial, so we can process the string greedily from left to right.

If we move from digit \(a\) to digit \(b\), the clockwise and counterclockwise distances add up to \(10\). Let \(d=|a-b|\), then the minimum cost of this move is \(\min(d, 10-d)\).

Starting from digit \(0\), we sum this minimum cost for every transition.

Let \(\textit{pre}\) be the previous digit under the pointer and \(\textit{cur}\) be the next target digit. Because the dial is circular, the shortest distance between them is

\[ \min\bigl(|\textit{cur}-\textit{pre}|, 10-|\textit{cur}-\textit{pre}|\bigr). \]

We iterate through the string, add this value to the answer, and update \(\textit{pre}\) to \(\textit{cur}\).

The time complexity is \(O(n)\), and the space complexity is \(O(1)\). Here, \(n\) is the length of \(s\).

1
2
3
4
5
6
7
8
class Solution:
    def minRotations(self, s: str) -> int:
        ans = pre = 0
        for cur in map(int, s):
            diff = abs(cur - pre)
            ans += min(diff, 10 - diff)
            pre = cur
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int minRotations(String s) {
        int ans = 0;
        int pre = 0;
        for (int i = 0; i < s.length(); ++i) {
            int cur = s.charAt(i) - '0';
            int diff = Math.abs(cur - pre);
            ans += Math.min(diff, 10 - diff);
            pre = cur;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int minRotations(string s) {
        int ans = 0;
        int pre = 0;
        for (int i = 0; i < s.size(); ++i) {
            int cur = s[i] - '0';
            int diff = abs(cur - pre);
            ans += min(diff, 10 - diff);
            pre = cur;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func minRotations(s string) int {
    ans := 0
    pre := 0
    for i := 0; i < len(s); i++ {
        cur := int(s[i] - '0')
        diff := abs(cur - pre)
        ans += min(diff, 10-diff)
        pre = cur
    }
    return ans
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function minRotations(s: string): number {
    let ans = 0;
    let pre = 0;
    for (let i = 0; i < s.length; ++i) {
        const cur = s.charCodeAt(i) - 48;
        const diff = Math.abs(cur - pre);
        ans += Math.min(diff, 10 - diff);
        pre = cur;
    }
    return ans;
}

Comments