What exactly makes a number good in Rotated Digits?

A number is good if every digit can be rotated to a valid digit and the resulting number differs from the original.

Why use state transition dynamic programming for this problem?

DP efficiently counts all valid good numbers up to n without iterating through every integer, handling digit-level constraints systematically.

Can I solve this with brute force?

Brute force is possible but inefficient for large n, as it must rotate every number individually.

How do I handle digits that remain the same after rotation?

Mark them as 'same' in your DP states; they do not make a number good but do not invalidate it either.

What are typical mistakes candidates make on Rotated Digits?

Common errors include misclassifying digits, failing to propagate DP states correctly, and counting unchanged numbers as good.

#788

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

旋转数字

我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。如果一个数的每位数字被旋转以后仍然还是一个数字，则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方（在这种情况下…

数学动态规划

题目描述

我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。

如果一个数的每位数字被旋转以后仍然还是一个数字，则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方（在这种情况下，它们以不同的方向旋转，换句话说，2 和 5 互为镜像）；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。

现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？

示例：

输入: 10
输出: 4
解释: 
在[1, 10]中有四个好数： 2, 5, 6, 9。
注意 1 和 10 不是好数, 因为他们在旋转之后不变。

提示：

N 的取值范围是 [1, 10000]。

lightbulb

解题思路

方法一：直接枚举

一种直观且有效的思路是，直接枚举 $[1,2,..n]$ 中的每个数，判断其是否为好数，若为好数，则答案加一。

那么题目的重点转化为如何判断一个数字 $x$ 是否为好数。判断的逻辑如下：

我们先用一个长度为 $10$ 的数组 $d$ 记录每个有效数字对应的旋转数字，在这道题中，有效数字有 $[0, 1, 8, 2, 5, 6, 9]$ ，分别对应旋转数字 $[0, 1, 8, 5, 2, 9, 6]$ 。如果不是有效数字，我们将对应的旋转数字设为 $-1$ 。

然后遍历数字 $x$ 的每一位数字 $v$ ，如果 $v$ 不是有效数字，说明 $x$ 不是好数，直接返回 $\textit{false}$ 。否则，我们将数字 $v$ 对应的旋转数字 $d[v]$ 加入到 $y$ 中。最后，判断 $x$ 和 $y$ 是否相等，若不相等，则说明 $x$ 是好数，返回 $\textit{true}$ 。

时间复杂度 $O(n \times \log n)$ ，其中 $n$ 为题目给定的数字。空间复杂度 $O(1)$ 。

相似题目：

1056. 易混淆数

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def rotatedDigits(self, n: int) -> int:
        def check(x):
            y, t = 0, x
            k = 1
            while t:
                v = t % 10
                if d[v] == -1:
                    return False
                y = d[v] * k + y
                k *= 10
                t //= 10
            return x != y

        d = [0, 1, 5, -1, -1, 2, 9, -1, 8, 6]
        return sum(check(i) for i in range(1, n + 1))

speed

复杂度分析

指标	值
时间	complexity depends on the number of digits in n, since DP iterates over each digit position with a fixed number of states per position, leading to O(d * s) where d is digits and s is state count. Space complexity is similarly O(d * s) for the DP table, often reducible to O(s) with state compression.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate correctly identifies invalid and changeable digits.
question_mark
Look for proper DP state definition that captures good number formation.
question_mark
Watch for attempts to brute-force the range instead of using transitions.

warning

常见陷阱

外企场景

error
Failing to mark digits 3, 4, 7 as invalid, which can overcount numbers.
error
Ignoring numbers that remain unchanged after rotation, counting them incorrectly as good.
error
Not correctly propagating DP states, leading to undercounting or overcounting sequences.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count rotated numbers in a different base, e.g., base-8 digits with custom rotation rules.
arrow_right_alt
Determine the largest good number less than or equal to n instead of counting all.
arrow_right_alt
Include additional digit transformation constraints, such as disallowing consecutive change digits.

help

常见问题

外企场景

继续练习

#805 数组的均值分割 #808 分汤 #837 新 21 点