Watch 10 video solutions for Rotated Digits, a medium level problem involving Math, Dynamic Programming. This walkthrough by Joey'sTech has 2,622 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
An integer x is a good if after rotating each digit individually by 180 degrees, we get a valid number that is different from x. Each digit must be rotated - we cannot choose to leave it alone.
A number is valid if each digit remains a digit after rotation. For example:
0, 1, and 8 rotate to themselves,2 and 5 rotate to each other (in this case they are rotated in a different direction, in other words, 2 or 5 gets mirrored),6 and 9 rotate to each other, andGiven an integer n, return the number of good integers in the range [1, n].
Example 1:
Input: n = 10 Output: 4 Explanation: There are four good numbers in the range [1, 10] : 2, 5, 6, 9. Note that 1 and 10 are not good numbers, since they remain unchanged after rotating.
Example 2:
Input: n = 1 Output: 0
Example 3:
Input: n = 2 Output: 1
Constraints:
1 <= n <= 104Problem Overview: You are given an integer n. A number is considered good if every digit remains valid after a 180° rotation and the rotated number becomes a different number. Digits 0,1,8 stay the same, 2↔5 and 6↔9 transform into each other, while 3,4,7 invalidate the number.
Approach 1: Direct Check Approach (O(n log n) time, O(1) space)
Iterate through every number from 1 to n. For each number, inspect its digits one by one using modulo and division. Track two conditions: whether all digits are valid after rotation, and whether at least one digit changes (2,5,6,9). If an invalid digit (3,4,7) appears, discard the number immediately. If the number contains a transforming digit and no invalid digits, count it as a good number. Each check scans the digits of the number, giving O(log n) per number and O(n log n) overall time with constant extra space. This approach is straightforward and relies mainly on digit manipulation from math fundamentals.
Approach 2: Digit-by-Digit Transformation Approach (Digit DP) (O(log n) time, O(log n) space)
Instead of checking every number individually, treat the number as a sequence of digits and count valid combinations using digit dynamic programming. Process digits from most significant to least significant while tracking two states: whether the prefix is already smaller than n, and whether a transforming digit (2,5,6,9) has appeared. Digits 0,1,8 keep the number unchanged, while 2,5,6,9 mark it as different after rotation. Digits 3,4,7 terminate the branch because they produce invalid rotations. This state-based counting avoids iterating through every integer and reduces the complexity to roughly O(d * states), where d is the number of digits in n. The technique is a classic example of dynamic programming applied to digits (often called digit DP).
Recommended for interviews: Start with the Direct Check approach to show you understand the digit rotation rules and validation logic. Interviewers often accept this O(n log n) solution because it is simple and correct. The Digit-by-Digit DP approach demonstrates stronger algorithmic thinking by counting valid patterns instead of brute-force checking every number.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Check Approach | O(n log n) | O(1) | Best for simple implementation and smaller n where checking each number is fast enough |
| Digit-by-Digit Transformation (Digit DP) | O(log n) | O(log n) | Preferred when optimizing counting problems involving digits or very large ranges |