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:

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

Input and Output

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?

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:

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.

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:

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: