788. Rotated Digits

Math
Dynamic Programming

TIME

O(n log n)

SPACE

O(1)

Intuition

A number can only be good if every digit is valid after rotation. Digits 0, 1, and 8 stay the same, while 2, 5, 6, and 9 change into another digit. Digits 3, 4, and 7 make the whole number invalid.

So a number is good when:

It contains no invalid digit.
It contains at least one digit that changes after rotation.

Approach

Check every number from 1 to n.

For each number, inspect its digits:

If any digit is one of 3, 4, or 7, the number is invalid.
If any digit is one of 2, 5, 6, or 9, the rotated number will differ from the original.

Count the number only when it is valid and has at least one changing digit.

Complexity

Time: O(n log n), each number contributes work proportional to its number of digits
Space: O(1), only constant extra state is used

Edge Cases

n = 1 → no good numbers
Numbers containing only 0, 1, and 8 → valid but unchanged, so not good
Numbers containing 3, 4, or 7 → invalid
Numbers with at least one of 2, 5, 6, or 9 and no invalid digits → good

Code

class Solution:
    def rotatedDigits(self, n: int) -> int:
        """
        788. Rotated Digits
        Time: O(n log n)
        Space: O(1)
        """
        invalid = {3, 4, 7}
        changes = {2, 5, 6, 9}

        def is_good(num: int) -> bool:
            has_change = False

            while num > 0:
                digit = num % 10
                if digit in invalid:
                    return False
                if digit in changes:
                    has_change = True
                num //= 10

            return has_change

        return sum(1 for num in range(1, n + 1) if is_good(num))

/**
 * 788. Rotated Digits
 * Time: O(n log n)
 * Space: O(1)
 */
class Solution {
    public int rotatedDigits(int n) {
        int count = 0;

        for (int num = 1; num <= n; num++) {
            if (isGood(num)) {
                count++;
            }
        }

        return count;
    }

    private boolean isGood(int num) {
        boolean hasChange = false;

        while (num > 0) {
            int digit = num % 10;

            if (digit == 3 || digit == 4 || digit == 7) {
                return false;
            }

            if (digit == 2 || digit == 5 || digit == 6 || digit == 9) {
                hasChange = true;
            }

            num /= 10;
        }

        return hasChange;
    }
}