Problem Description

The Rotated Digits problem asks: Given a positive integer N, count how many numbers in the range 1 to N (inclusive) are "good" after being rotated 180 degrees.

A number is good if, after rotating each of its digits by 180 degrees, it becomes a valid and different number.

• Valid digits when rotated: 0, 1, 2, 5, 6, 8, 9
• Invalid digits: 3, 4, 7 (if any of these are present, the number is not good)
• Digits 0, 1, 8 remain the same after rotation
• Digits 2 <-> 5 and 6 <-> 9 change to each other
• A "good" number must change to a different number after rotation

Example: For N = 10, the good numbers are 2, 5, 6, 9 (since they change to 5, 2, 9, 6 respectively).

Thought Process

To solve this problem, we first need to identify which digits are valid when rotated, and which digits cause the number to become invalid. We also need to make sure that the number actually changes after rotation (so numbers made up only of 0, 1, 8 are not counted, since they look the same).

The brute-force approach is to check every number from 1 to N:

• For each number, examine each digit to ensure all are valid after rotation.
• Track if at least one digit actually changes (so the rotated number is different).
• If all digits are valid and at least one changes, count the number as "good".

To optimize, we can use properties of digits and possibly precompute results for all numbers up to N, or use dynamic programming to avoid repeating work.

Solution Approach

Let's break down the solution step-by-step:

1. Identify Valid and Changed Digits:
   • Valid digits: 0, 1, 2, 5, 6, 8, 9
   • Changing digits: 2, 5, 6, 9 (these digits become different digits after rotation)
2. Iterate Over Each Number:
   • For each number from 1 to N, process all its digits.
   • If any digit is invalid (3, 4, 7), skip this number.
   • If at least one digit is a "changing" digit (2, 5, 6, 9), mark the number as "good".
3. Count Good Numbers:
   • Keep a counter for all numbers that are "good" as per the rules above.
4. Optimization:
   • For large N, we can use a DP array where dp[i] stores the state for number i:
   • 0: invalid number (contains invalid digits)
   • 1: valid but not good (only contains 0, 1, 8)
   • 2: good number (contains at least one changing digit)
   • Build up dp[i] from dp[i // 10] and the last digit.

This approach is efficient because it avoids recomputing for overlapping subproblems, and only checks each digit a fixed number of times.

Example Walkthrough

Let's take N = 10 and walk through the numbers:

• 1: Digits = [1] → valid, but unchanged → not good
• 2: Digits = [2] → valid, and changes to 5 → good
• 3: Digits = [3] → invalid → skip
• 4: Digits = [4] → invalid → skip
• 5: Digits = [5] → valid, and changes to 2 → good
• 6: Digits = [6] → valid, and changes to 9 → good
• 7: Digits = [7] → invalid → skip
• 8: Digits = [8] → valid, but unchanged → not good
• 9: Digits = [9] → valid, and changes to 6 → good
• 10: Digits = [1, 0] → both valid, but unchanged → not good

So, for N = 10, the good numbers are 2, 5, 6, 9. The answer is 4.

Time and Space Complexity

Brute-force approach:

• For each number up to N, we check each digit (up to log₁₀(N) digits per number).
• Time Complexity: O(N log N)
• Space Complexity: O(1) (no extra structures needed)

• We use a DP array of size N+1 to store the state of each number.
• Time Complexity: O(N) (since each number is processed using previously computed results)
• Space Complexity: O(N) (for the DP array)

The DP approach is faster for large N because it avoids redundant digit checks.

Summary

The Rotated Digits problem is about counting numbers between 1 and N that remain valid and change to a different number when each digit is rotated 180 degrees. By carefully checking each digit and using dynamic programming to store intermediate results, we can efficiently solve the problem for large N. The key insight is to distinguish between digits that are valid, those that cause a change, and those that make a number invalid, and to use this information to build up the solution efficiently.

Code Implementation

class Solution:
    def rotatedDigits(self, N: int) -> int:
        # 0: invalid, 1: valid but unchanged, 2: good (valid and changes)
        dp = [0] * (N + 1)
        count = 0
        for i in range(1, N + 1):
            a, b = dp[i // 10], dp[i % 10]
            if a == 0 and i >= 10:
                dp[i] = 0
            elif b == 0:
                dp[i] = 0
            elif a == 1 and b == 1:
                dp[i] = 1
            else:
                dp[i] = 2
            if dp[i] == 2:
                count += 1
        return count
      

class Solution {
public:
    int rotatedDigits(int N) {
        vector<int> dp(N + 1, 0);
        int count = 0;
        for (int i = 1; i <= N; ++i) {
            int a = dp[i / 10], b = dp[i % 10];
            if (i >= 10 && a == 0) {
                dp[i] = 0;
            } else if (b == 0) {
                dp[i] = 0;
            } else if (a == 1 && b == 1) {
                dp[i] = 1;
            } else {
                dp[i] = 2;
            }
            if (dp[i] == 2) ++count;
        }
        return count;
    }
};
      

class Solution {
    public int rotatedDigits(int N) {
        int[] dp = new int[N + 1];
        int count = 0;
        for (int i = 1; i <= N; ++i) {
            int a = dp[i / 10], b = dp[i % 10];
            if (i >= 10 && a == 0) {
                dp[i] = 0;
            } else if (b == 0) {
                dp[i] = 0;
            } else if (a == 1 && b == 1) {
                dp[i] = 1;
            } else {
                dp[i] = 2;
            }
            if (dp[i] == 2) count++;
        }
        return count;
    }
}
      

var rotatedDigits = function(N) {
    let dp = new Array(N + 1).fill(0);
    let count = 0;
    for (let i = 1; i <= N; ++i) {
        let a = dp[Math.floor(i / 10)], b = dp[i % 10];
        if (i >= 10 && a === 0) {
            dp[i] = 0;
        } else if (b === 0) {
            dp[i] = 0;
        } else if (a === 1 && b === 1) {
            dp[i] = 1;
        } else {
            dp[i] = 2;
        }
        if (dp[i] === 2) count++;
    }
    return count;
};