LeetCode 788 - Rotated Digits

LeetCode Problem 788

Difficulty: 🟡 Medium
Topics: Math, Dynamic Programming

Solution

Problem Understanding

The problem asks us to count the number of good integers within a given range [1, n]. An integer is considered good if each of its digits, when rotated 180 degrees, forms another valid digit and the resulting number is different from the original. The digits 0, 1, and 8 remain the same when rotated, while 2 and 5 swap, and 6 and 9 swap. Any number containing digits 3, 4, or 7 is invalid after rotation.

The input n is a single integer, and the output should be the total count of good integers in [1, n]. Constraints indicate 1 <= n <= 10^4, which means a solution that iterates through all numbers is feasible but may not be the most efficient. Edge cases to consider include small values of n (like 1 or 2), numbers that are valid but remain unchanged after rotation (like 1, 8, 10), and numbers containing invalid digits like 3 or 7.

Approaches

The brute-force approach is straightforward: iterate through all numbers from 1 to n, convert each number to its rotated version, and check if it is valid and different from the original. This works for the given constraints because n is at most 10^4, but it does not scale well if n were larger.

The key insight for a more optimal solution is recognizing that the problem can be solved using dynamic programming on digits or categorical counting. Each digit can be classified as unchanged (0, 1, 8), good (2, 5, 6, 9), or invalid (3, 4, 7). A number is good if it contains at least one good digit and no invalid digits. We can iterate through numbers and apply this classification without generating the rotated number explicitly.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * log n)	O(log n)	Convert each number to string, check each digit, count good numbers
Optimal	O(n * d)	O(1)	Iterate through numbers, classify digits, count if contains at least one good digit

Algorithm Walkthrough

1. Initialize a counter count to 0. This will hold the total number of good numbers.

2. Define a set of good digits (2, 5, 6, 9) and a set of valid digits (0, 1, 2, 5, 6, 8, 9).

3. Iterate over each integer num from 1 to n. For each number:

4. Convert num to a string and check each digit.

5. If any digit is invalid (3, 4, 7), skip this number.

6. Track if the number contains at least one good digit.

7. If it does, increment count.

8. Return count after finishing the iteration.

Why it works: Every number is either invalid, unchanged, or good. By iterating through all numbers, checking validity, and ensuring at least one good digit, we precisely count the numbers that meet the problem’s definition of good integers.

Python Solution

class Solution:
    def rotatedDigits(self, n: int) -> int:
        good_digits = {'2', '5', '6', '9'}
        valid_digits = {'0', '1', '2', '5', '6', '8', '9'}
        count = 0
        
        for num in range(1, n + 1):
            num_str = str(num)
            is_good = False
            for ch in num_str:
                if ch not in valid_digits:
                    is_good = False
                    break
                if ch in good_digits:
                    is_good = True
            if is_good:
                count += 1
                
        return count

This implementation iterates through every number from 1 to n. For each number, it checks each digit to see if it is valid. If it encounters an invalid digit, it skips the number. Otherwise, it checks if there is at least one digit that qualifies as good. If so, it increments the counter.

Go Solution

func rotatedDigits(n int) int {
    goodDigits := map[rune]bool{'2': true, '5': true, '6': true, '9': true}
    validDigits := map[rune]bool{'0': true, '1': true, '2': true, '5': true, '6': true, '8': true, '9': true}
    
    count := 0
    
    for num := 1; num <= n; num++ {
        numStr := []rune(fmt.Sprintf("%d", num))
        isGood := false
        valid := true
        for _, ch := range numStr {
            if !validDigits[ch] {
                valid = false
                break
            }
            if goodDigits[ch] {
                isGood = true
            }
        }
        if valid && isGood {
            count++
        }
    }
    
    return count
}

In Go, we handle numbers by converting them to a slice of runes to iterate each digit. We use two maps for good and valid digits. The logic mirrors the Python version. Since Go has no implicit boolean short-circuiting with strings, we explicitly track valid and isGood.

Worked Examples

Example 1: n = 10

num	digits	valid?	has_good?	count
1	1	Yes	No	0
2	2	Yes	Yes	1
3	3	No	-	1
4	4	No	-	1
5	5	Yes	Yes	2
6	6	Yes	Yes	3
7	7	No	-	3
8	8	Yes	No	3
9	9	Yes	Yes	4
10	10	Yes	No	4

Output: 4

Example 2: n = 1 → Output: 0

Example 3: n = 2 → Output: 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n * log n)	We iterate from 1 to n, converting each number to string with log10(n) digits
Space	O(1)	Only constant extra space is used for sets/maps and counters

Even though the conversion to string takes logarithmic time, n <= 10^4 ensures this is efficient enough.

Test Cases

# Provided examples
assert Solution().rotatedDigits(10) == 4  # basic example
assert Solution().rotatedDigits(1) == 0   # smallest input
assert Solution().rotatedDigits(2) == 1   # single good number

# Edge cases
assert Solution().rotatedDigits(0) == 0   # below valid range
assert Solution().rotatedDigits(857) >= 0 # large n to test performance
assert Solution().rotatedDigits(10000) >= 0 # maximum constraint

# Specific cases
assert Solution().rotatedDigits(6) == 3   # numbers 2, 5, 6
assert Solution().rotatedDigits(11) == 4  # numbers 2, 5, 6, 9

Test	Why
10	Basic example with small numbers
1	Edge case where no good numbers exist
2	Single good number
0	Input below valid range
857	Tests efficiency on mid-sized input
10000	Tests upper bound of constraint
6	Checks inclusion of number equal to a good digit
11	Checks behavior across tens boundary

Edge Cases

1. Smallest numbers (n = 1): This is important because the answer is 0, testing that the algorithm does not incorrectly include unchanged numbers. The solution handles this by requiring at least one good digit.
2. Numbers containing invalid digits (3, 4, 7): These must be skipped. The algorithm explicitly breaks the loop when an invalid digit is detected, preventing incorrect counting.
3. Numbers with all digits unchanged (0, 1, 8): These numbers are valid but not good. The implementation only increments the count if there is at least one good digit, ensuring unchanged numbers are excluded.

This approach guarantees correctness across all edge scenarios while remaining efficient for the problem constraints.