#788

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Rotated Digits

Count all integers from 1 to n that transform into a different valid number when each digit is rotated 180 degrees using DP.

math dynamic programming

Problem Statement

A positive integer x is considered good if, after rotating each digit individually by 180 degrees, it becomes a valid number different from x. Each digit must be rotated and cannot be left unchanged. Digits 0, 1, 8 remain themselves, 2 and 5 swap, 6 and 9 swap, while 3, 4, 7 become invalid.

Given a positive integer n, compute the total number of good integers in the range [1, n]. For example, for n = 10, the good numbers are 2, 5, 6, and 9. Your solution must handle large n efficiently by leveraging state transition dynamic programming rather than naive enumeration.

Examples

Example 1

Input: n = 10

Output: 4

There are four good numbers in the range [1, 10] : 2, 5, 6, 9. Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.

Example 2

Input: n = 1

Output: 0

Example details omitted.

Example 3

Input: n = 2

Output: 1

Example details omitted.

Constraints

1 <= n <= 104

Solution Approach

Classify Digits

Identify digits as invalid, same, or change after rotation. This classification sets up the DP states, where invalid digits block the number from being good, same digits maintain the previous state, and change digits enable a number to be counted as good.

State Transition DP

Define DP states to track counts of numbers up to each digit position, including whether a good digit has appeared. Transition states for each new digit according to its class, accumulating counts of good numbers while skipping invalid sequences. This ensures all numbers up to n are considered efficiently.

Combine Counts and Return

After filling the DP table, sum all states that include at least one change digit and contain no invalid digits. Return this sum as the total count of good numbers in [1, n]. This approach avoids iterating over each integer directly and scales to large n.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Direct Enumeration

An intuitive and effective approach is to directly enumerate each number in $[1,2,..n]$ and determine whether it is a good number. If it is a good number, increment the answer by one.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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))

Solution 2: Digit DP

Solution 1 is sufficient to solve this problem, but its time complexity is relatively high. If the data range of the problem reaches the level of $10^9$, the approach in Solution 1 will exceed the time limit.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

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))

Continue Practicing

#805 split array with same average #808 soup servings #837 new 21 game