788. Rotated Digits

Problem Description

Given an integer n, find the number of "good" integers in the range [1, n]. A "good" integer is defined as an integer where after rotating each digit individually by 180 degrees, we get a valid number that is different from the original number. Valid digits after rotation are 0, 1, 8, and the pairs (2, 5) and (6, 9).

Solution Approaches

Two approaches are presented here: direct enumeration and digit dynamic programming (DP).

Solution 1: Direct Enumeration

This approach iterates through each number from 1 to n and checks if it's a "good" number. The check involves:

1. Rotation Mapping: Create a mapping to handle digit rotation (e.g., 2 maps to 5, 5 maps to 2, etc.). Invalid rotations map to -1.
2. Rotation and Comparison: For each number, rotate its digits using the mapping. If the rotated number is valid (no -1s in the mapping) and different from the original, it's a "good" number.

Time Complexity: O(n log n) - iterating through n numbers, and the rotation check takes O(log n) time due to digit processing. Space Complexity: O(1) - constant extra space is used.

Code (Python):

class Solution:
    def rotatedDigits(self, n: int) -> int:
        d = [0, 1, 5, -1, -1, 2, 9, -1, 8, 6]  # Rotation mapping
 
        def check(x):
            y, t = 0, x
            k = 1
            while t:
                v = t % 10
                if d[v] == -1:
                    return False # Invalid rotation
                y = d[v] * k + y
                k *= 10
                t //= 10
            return x != y # Different from original
 
        return sum(check(i) for i in range(1, n + 1))
 

Other languages (Java, C++, Go, TypeScript) would follow a similar structure.

Solution 2: Digit Dynamic Programming

This approach is more efficient for larger values of n. It uses dynamic programming to count good numbers without explicitly iterating through each number.

The core idea is a recursive function dfs(i, ok, limit):

• i: Current digit position (from most significant to least significant).
• ok: Boolean indicating if a good digit has been encountered so far (true if at least one rotated digit is different from original).
• limit: Boolean indicating whether current digit is constrained by the input number n.

The recursion explores possible digits at each position, considering valid rotations and constraints from n. The base case is when all digits have been processed.

Time Complexity: O(log n) - the number of digits in n determines the recursion depth. Space Complexity: O(log n) - due to recursion depth and potentially memoization.

Code (Python):

class Solution:
    def rotatedDigits(self, n: int) -> int:
        s = str(n)
        @cache # memoization for efficiency
        def dfs(i, ok, limit):
            if i == len(s):
                return ok
            up = int(s[i]) if limit else 9
            ans = 0
            for j in range(up + 1):
                if j in (0, 1, 8):
                    ans += dfs(i + 1, ok, limit and j == up)
                elif j in (2, 5, 6, 9):
                    ans += dfs(i + 1, 1, limit and j == up)
            return ans
        return dfs(0, 0, True)

Similar code structures can be implemented in other languages (Java, C++, Go, TypeScript) using memoization techniques to optimize performance. The Java and C++ examples explicitly show memoization using arrays or @cache as appropriate. Other languages may require different memoization approaches based on language features.

Conclusion

While the direct enumeration approach is simpler to understand, digit DP offers significantly better performance for larger inputs. The choice depends on the expected input size and performance requirements.