# LeetCode 788: Rotated Digits

## Problem Restatement

We are given an integer `n`.

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

```python
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:

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

## Examples

Example 1:

```python
n = 10
```

Check numbers from `1` to `10`.

The good numbers are:

```text
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:

```python
4
```

Example 2:

```python
n = 1
```

The only number is `1`.

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

The answer is:

```python
0
```

Example 3:

```python
n = 2
```

The numbers are `1` and `2`.

Only `2` is good.

The answer is:

```python
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:

```python
101
```

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

A number like:

```python
102
```

is good because `2` rotates to `5`.

A number like:

```python
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:

```python
O(n log n)
```

## Implementation

```python
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:

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

A number with any invalid digit cannot be good:

```python
if digit in invalid:
    return False
```

A number with a changing digit may be good:

```python
if digit in changed:
    has_changed_digit = True
```

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

```python
return has_changed_digit
```

Then we check every number in the range:

```python
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:

```python
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.

```python
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

```python
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 |