LeetCode 788: Rotated Digits

Problem Restatement

We are given an integer n.

We need to count how many integers x in the range:

1 <= x <= n

are good numbers.

A number is good if, after rotating every digit by 180 degrees, we get:

1. A valid number.
2. A different number from the original.

The valid digit rotations are:

Digit	Rotates to
0	0
1	1
2	5
5	2
6	9
8	8
9	6

Digits 3, 4, and 7 become invalid after rotation.

Input and Output

Item	Meaning
Input	Integer n
Output	Count of good numbers from 1 to n
Valid unchanged digits	0, 1, 8
Valid changed digits	2, 5, 6, 9
Invalid digits	3, 4, 7

Function shape:

class Solution:
    def rotatedDigits(self, n: int) -> int:
        ...

Examples

Example 1:

n = 10

Check numbers from 1 to 10.

The good numbers are:

2, 5, 6, 9

Why?

Number	Rotated	Good?
1	1	No, unchanged
2	5	Yes
5	2	Yes
6	9	Yes
8	8	No, unchanged
9	6	Yes
10	10	No, unchanged

So the answer is:

4

Example 2:

n = 1

The only number is 1.

After rotation, it is still 1, so it is not good.

The answer is:

0

Example 3:

n = 2

The numbers are 1 and 2.

Only 2 is good.

The answer is:

1

First Thought: Rotate Every Number

The simplest method is to check every number from 1 to n.

For each number:

1. Look at each digit.
2. If any digit is invalid, the number is not good.
3. Track whether at least one digit changes after rotation.
4. If all digits are valid and at least one digit changes, count it.

This is direct and easy to implement.

Key Insight

A number is good exactly when both conditions hold:

Condition	Meaning
No invalid digits	It contains no 3, 4, or 7
At least one changing digit	It contains at least one of 2, 5, 6, or 9

Digits 0, 1, and 8 are valid but do not change the number.

So a number like:

101

is valid after rotation, but unchanged. It is not good.

A number like:

102

is good because 2 rotates to 5.

A number like:

123

is invalid because 3 cannot rotate into a digit.

Algorithm

1. Initialize answer = 0.
2. For each number x from 1 to n:
   1. Check whether x is good.
   2. If yes, increment answer.
3. Return answer.

To check whether a number is good:

1. Convert it to a string.
2. For each digit:
   1. If it is in 3, 4, or 7, return False.
   2. If it is in 2, 5, 6, or 9, mark that the number changes.
3. Return whether the number changes.

Correctness

A number is valid after rotation only if every digit has a valid rotated form. The digits with valid rotated forms are exactly 0, 1, 2, 5, 6, 8, and 9. Therefore, if the algorithm sees 3, 4, or 7, it correctly rejects the number.

A valid rotated number is different from the original exactly when at least one digit changes. The digits that change are exactly 2, 5, 6, and 9. The digits 0, 1, and 8 remain the same.

The algorithm counts a number only when it has no invalid digit and has at least one changing digit. These are exactly the conditions for being a good number. Since it checks every number from 1 to n, it returns the correct count.

Complexity

Let d be the number of digits in n.

Metric	Value	Why
Time	O(n * d)	We check up to d digits for each number
Space	O(d)	String conversion stores the digits of one number

Since d = O(log n), the time complexity can also be written as:

O(n log n)

Implementation

class Solution:
    def rotatedDigits(self, n: int) -> int:
        changed = {"2", "5", "6", "9"}
        invalid = {"3", "4", "7"}

        def is_good(x: int) -> bool:
            has_changed_digit = False

            for digit in str(x):
                if digit in invalid:
                    return False

                if digit in changed:
                    has_changed_digit = True

            return has_changed_digit

        answer = 0

        for x in range(1, n + 1):
            if is_good(x):
                answer += 1

        return answer

Code Explanation

We separate the important digit groups:

changed = {"2", "5", "6", "9"}
invalid = {"3", "4", "7"}

A number with any invalid digit cannot be good:

if digit in invalid:
    return False

A number with a changing digit may be good:

if digit in changed:
    has_changed_digit = True

At the end, the number is good only if it had at least one changing digit:

return has_changed_digit

Then we check every number in the range:

for x in range(1, n + 1):
    if is_good(x):
        answer += 1

Alternative: Digit State DP

There is also a compact dynamic programming approach.

Classify each number by state:

State	Meaning
0	Valid so far, but unchanged
1	Valid and changed
2	Invalid

For a number x, let:

dp[x]

describe whether x is invalid, valid unchanged, or valid changed.

We can derive dp[x] from dp[x // 10] and the last digit.

class Solution:
    def rotatedDigits(self, n: int) -> int:
        status = [0] * (n + 1)
        answer = 0

        for x in range(1, n + 1):
            last = x % 10
            rest = x // 10

            if last in (3, 4, 7) or status[rest] == 2:
                status[x] = 2
            elif last in (2, 5, 6, 9) or status[rest] == 1:
                status[x] = 1
                answer += 1
            else:
                status[x] = 0

        return answer

This has the same linear scan over numbers, but avoids converting each number to a string.

Testing

def run_tests():
    s = Solution()

    assert s.rotatedDigits(1) == 0
    assert s.rotatedDigits(2) == 1
    assert s.rotatedDigits(10) == 4

    assert s.rotatedDigits(20) == 9
    assert s.rotatedDigits(100) == 40

    assert s.rotatedDigits(3) == 1
    assert s.rotatedDigits(8) == 3

    print("all tests passed")

run_tests()

Test coverage:

Test	Why
n = 1	Only unchanged valid digit
n = 2	First good number appears
n = 10	Standard example
n = 20	Checks two-digit numbers
n = 100	Checks larger range
n = 3	Includes first invalid digit
n = 8	Mix of changed, unchanged, and invalid digits