Practice/Microsoft/Leetcode 788. Rotated Digits

Leetcode 788. Rotated Digits

CodingMust

Problem

When you rotate certain digits by 180 degrees, they transform into different valid digits. Specifically:

• 0, 1, and 8 remain the same after rotation
• 2 becomes 5, and 5 becomes 2
• 6 becomes 9, and 9 becomes 6
• 3, 4, and 7 become invalid (not recognizable digits)

A number is considered "good" if:

1. All of its digits can be rotated (i.e., it contains no 3, 4, or 7)
2. After rotation, it forms a different number (i.e., it must contain at least one of {2, 5, 6, 9})

Given a positive integer n, count how many numbers in the range [1, n] are "good" numbers.

Requirements

1. Validate that each number contains only digits that can be rotated: 0, 1, 2, 5, 6, 8, 9
2. Ensure the number contains at least one digit that changes after rotation: 2, 5, 6, or 9
3. Count all such valid numbers from 1 to n inclusive
4. Return the total count as an integer

Constraints

• 1 ≤ n ≤ 10,000
• The solution should efficiently handle the upper range
• Expected time complexity: O(n) or better with digit-wise analysis
• Expected space complexity: O(1) for iterative approaches, O(log n) for recursive approaches

Examples

Example 1:

` Input: n = 10 Output: 4 Explanation: The valid numbers are 2, 5, 6, and 9.

• 1, 8 contain only self-mapping digits (not different after rotation)
• 3, 4, 7 contain invalid digits
• 10 contains 1 and 0, both self-mapping (not different after rotation) `

Example 2:

Input: n = 857 Output: 247 Explanation: Count all numbers from 1 to 857 that contain only rotatable digits and at least one changing digit.

Example 3:

Input: n = 25 Output: 10 Explanation: Valid numbers are 2, 5, 6, 9, 12, 15, 16, 19, 20, 25. Each contains at least one of \{2, 5, 6, 9\} and no invalid digits.