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.
In this approach, iterate over each number from 1 to n, and check if it is a good number by evaluating each digit against set rules. A good number must transform into a valid and different number after rotating each digit 180 degrees. Maintain two sets, one for valid but identical digits and another for valid and different digits, to effectively check for goodness.
The C code defines two functions: isGoodNumber and rotatedDigits. isGoodNumber checks if a number is good by evaluating its digits against the rules, and rotatedDigits counts how many good numbers exist from 1 to n by iterating and checking each.
Time Complexity: O(n * d), where d is the number of digits in n.
Space Complexity: O(1), as we use a constant amount of space.
This is a more optimization-focused method where instead of iterating through the entire set of numbers, transformations of digits are pre-calculated using lookup tables. The process involves analyzing each number only once and determining if at least one digit can ensure the number transforms to a valid and different form.
The C approach uses a lookup table to quickly transform digits. It checks if the transformed number is different from the original to determine 'goodness'.
Time Complexity: O(n * d), where d is the number of digits in n.
Space Complexity: O(1), using constant extra space for lookup.
An intuitive and effective approach is to directly enumerate each number in [1,2,..n] and determine whether it is a good number. If it is a good number, increment the answer by one.
The key to the problem is how to determine whether a number x is a good number. The logic is as follows:
We first use an array d of length 10 to record the rotated digits corresponding to each valid digit. In this problem, the valid digits are [0, 1, 8, 2, 5, 6, 9], which correspond to the rotated digits [0, 1, 8, 5, 2, 9, 6] respectively. If a digit is not valid, we set the corresponding rotated digit to -1.
Then, we traverse each digit v of the number x. If v is not a valid digit, it means x is not a good number, and we directly return false. Otherwise, we add the rotated digit d[v] corresponding to the digit v to y. Finally, we check whether x and y are equal. If they are not equal, it means x is a good number, and we return true.
The time complexity is O(n times log n), where n is the given number. The space complexity is O(1).
Similar problems:
Python
Java
C++
Go
TypeScript
Solution 1 is sufficient to solve this problem, but its time complexity is relatively high. If the data range of the problem reaches the level of 10^9, the approach in Solution 1 will exceed the time limit.
This problem essentially asks for the number of numbers in the given range [l, ..r] that satisfy certain conditions. The conditions are related to the composition of the numbers rather than their size, so we can use the concept of Digit DP to solve it. In Digit DP, the size of the number has little impact on the complexity.
For the range [l, ..r] problem, we generally convert it to the problem of [1, ..r] and then subtract the result of [1, ..l - 1], i.e.:
$
ans = sum_{i=1}^{r} ans_i - sum_{i=1}^{l-1} ans_i
However, for this problem, we only need to find the value for the range [1, ..r].
Here, we use memoized search to implement Digit DP. We search from the starting point downwards, and at the lowest level, we get the number of solutions. We then return the answers layer by layer upwards, and finally get the final answer from the starting point of the search.
The basic steps are as follows:
We convert the number n to a string s. Then we define a function dfs(i, ok, limit), where i represents the digit position, ok indicates whether the current number satisfies the problem's conditions, and limit is a boolean indicating whether the digits that can be filled are restricted.
The function executes as follows:
If i is greater than or equal to the length of the string s, return ok;
Otherwise, we get the current digit up. If limit is true, up is the current digit; otherwise, up is 9;
Next, we iterate over [0, ..up]. If j is a valid digit [0, 1, 8], we recursively call dfs(i + 1, ok, limit \land j = up); if j is a valid digit [2, 5, 6, 9], we recursively call dfs(i + 1, 1, limit \land j = up). We sum all the results of the recursive calls and return.
The time complexity is O(log n times D), and the space complexity is O(log n). Here, D = 10$.
Similar problems:
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Direct Check Approach | Time Complexity: O(n * d), where d is the number of digits in n. |
| Digit-by-Digit Transformation Approach | Time Complexity: O(n * d), where d is the number of digits in n. |
| Direct Enumeration | — |
| Digit DP | — |
| 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 |
Rotated Digits | Dynamic Programming | Leetcode#788 • Joey'sTech • 2,622 views views
Watch 9 more video solutions →Practice Rotated Digits with our built-in code editor and test cases.
Practice on FleetCode