Skip to content

4071. Minimum Rotations to Dial a Number II

SourceWeekly Contest 522 Q2DifficultyMediumRating1579

Description

You are given an integer n and a string s of length n 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.

Before dialing, you may perform the following operation at most once:

  • Choose an index k such that 0 <= k < n and reverse the suffix s[k..n - 1].

Return the minimum total number of rotations needed to dial the string after optimally choosing whether to perform the operation and which suffix to reverse.

 

Example 1:

Input: n = 4, s = "1502"

Output: 9

Explanation:

Reverse the suffix starting at k = 1 to obtain "1205", then dial it.

Step From To Rotations
1 0 1 1
2 1 2 1
3 2 0 2
4 0 5 5

The total is 1 + 1 + 2 + 5 = 9, which is the minimum total number of rotations.

Example 2:

Input: n = 4, s = "2916"

Output: 12

Explanation:

Choose not to reverse a suffix and dial "2916".

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

The total is 2 + 3 + 2 + 5 = 12, which is the minimum total number of rotations.

Example 3:

Input: n = 4, s = "4219"

Output: 6

Explanation:

Reverse the suffix starting at k = 0, which reverses the entire string, to obtain "9124", then dial it.

Step From To Rotations
1 0 9 1
2 9 1 2
3 1 2 1
4 2 4 2

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

 

Constraints:

  • 1 <= n == s.length <= 105​​​​​​​
  • s consists only of digits '0' to '9'

Solutions

Solution 1

Thinking

Without reversing anything, the total cost is the distance from \(0\) to the first digit plus the sum of distances between adjacent digits.

Reversing a suffix changes the order inside the suffix, but every adjacent pair inside that suffix is still the same unordered pair, so the total internal suffix cost does not change.

Therefore, for each split point \(k\), only two parts may change: which digit is dialed first, and the single edge connecting the prefix to the suffix. This gives an \(O(1)\) transition per split.

Define the total rotation cost between adjacent digits as \(T\):

\[ T=\sum_{i=1}^{n-1} \operatorname{dist}(s[i-1], s[i]), \]

where \(\operatorname{dist}(a,b)\) is the shortest circular distance between digits \(a\) and \(b\).

If we reverse the whole string, namely \(k=0\), the answer becomes

\[ \operatorname{dist}(0, s[n-1]) + T. \]

If \(k>0\), the prefix \(s[0..k-1]\) stays in place, and all internal edges of the suffix keep the same total contribution. The only replaced edge is \((s[k-1], s[k])\), which becomes \((s[k-1], s[n-1])\). The starting digit is still \(s[0]\), so the total cost is

\[ T - \operatorname{dist}(s[k-1], s[k]) + \operatorname{dist}(0, s[0]) + \operatorname{dist}(s[k-1], s[n-1]). \]

We enumerate all split points and take the minimum.

The time complexity is \(O(n)\), and the space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def minRotations(self, n: int, s: str) -> int:
        def dist(a: str, b: str) -> int:
            d = abs(ord(a) - ord(b))
            return min(d, 10 - d)

        total = sum(dist(a, b) for a, b in pairwise(s))

        first = s[0]
        last = s[-1]
        to_first = dist("0", first)
        ans = total + dist("0", last)

        for pre, cur in pairwise(s):
            ans = min(ans, total - dist(pre, cur) + to_first + dist(pre, last))

        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int minRotations(int n, String s) {
        int total = 0;
        for (int i = 1; i < n; ++i) {
            int diff = Math.abs(s.charAt(i) - s.charAt(i - 1));
            total += Math.min(diff, 10 - diff);
        }

        char first = s.charAt(0);
        char last = s.charAt(n - 1);
        int toFirst = Math.min(first - '0', 10 - (first - '0'));
        int ans = total + Math.min(last - '0', 10 - (last - '0'));

        for (int i = 1; i < n; ++i) {
            char pre = s.charAt(i - 1);
            char cur = s.charAt(i);
            int diff = Math.abs(pre - cur);
            int edge = Math.min(diff, 10 - diff);
            diff = Math.abs(pre - last);
            int toLast = Math.min(diff, 10 - diff);
            ans = Math.min(ans, total - edge + toFirst + toLast);
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int minRotations(int n, string s) {
        int total = 0;
        for (int i = 1; i < n; ++i) {
            int diff = abs(s[i] - s[i - 1]);
            total += min(diff, 10 - diff);
        }

        char first = s[0];
        char last = s[n - 1];
        int toFirst = min(first - '0', 10 - (first - '0'));
        int ans = total + min(last - '0', 10 - (last - '0'));

        for (int i = 1; i < n; ++i) {
            char pre = s[i - 1];
            char cur = s[i];
            int diff = abs(pre - cur);
            int edge = min(diff, 10 - diff);
            diff = abs(pre - last);
            int toLast = min(diff, 10 - diff);
            ans = min(ans, total - edge + toFirst + toLast);
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func minRotations(n int, s string) int {
    total := 0
    for i := 1; i < n; i++ {
        diff := int(s[i]) - int(s[i-1])
        if diff < 0 {
            diff = -diff
        }
        total += min(diff, 10-diff)
    }

    first := int(s[0] - '0')
    last := int(s[n-1] - '0')
    toFirst := min(first, 10-first)
    ans := total + min(last, 10-last)

    for i := 1; i < n; i++ {
        pre := int(s[i-1])
        cur := int(s[i])
        diff := cur - pre
        if diff < 0 {
            diff = -diff
        }
        edge := min(diff, 10-diff)

        diff = pre - int(s[n-1])
        if diff < 0 {
            diff = -diff
        }
        toLast := min(diff, 10-diff)

        ans = min(ans, total-edge+toFirst+toLast)
    }

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function minRotations(n: number, s: string): number {
    let total = 0;
    for (let i = 1; i < n; ++i) {
        const diff = Math.abs(s.charCodeAt(i) - s.charCodeAt(i - 1));
        total += Math.min(diff, 10 - diff);
    }

    const first = s[0];
    const last = s[n - 1];
    const toFirst = Math.min(first.charCodeAt(0) - 48, 10 - (first.charCodeAt(0) - 48));
    let ans = total + Math.min(last.charCodeAt(0) - 48, 10 - (last.charCodeAt(0) - 48));

    for (let i = 1; i < n; ++i) {
        const pre = s[i - 1];
        const cur = s[i];
        const diff = Math.abs(pre.charCodeAt(0) - cur.charCodeAt(0));
        const edge = Math.min(diff, 10 - diff);
        const toLastDiff = Math.abs(pre.charCodeAt(0) - last.charCodeAt(0));
        const toLast = Math.min(toLastDiff, 10 - toLastDiff);
        ans = Math.min(ans, total - edge + toFirst + toLast);
    }

    return ans;
}

Comments