Rotated Digits solution and explanation
Google
9 more videos on this problem
Rotated Digits | 3 Approached | Simplified | Detailed | Leetcode 788 | codestorywithMIKcodestorywithMIK · 28:50 · 6K views
Rotated Digits | Dynamic Programming | Leetcode#788Joey'sTech · 11:42 · 2K views
788. Rotated Digits (Leetcode Easy)Programming Live with Larry · 9:11 · 2K views
leetcode 788 | Rotated Digits | Leetcode POTD | Digit Dynamic Programming | DSACode With Vick · 16:26 · 1K views
#9 leetcode 788. Rotated Digits9527 focus · 4:40 · 828 views
Leetcode solving: 788. Rotated DigitsMath Geeks · 2:26 · 668 views
Rotated Digits | Leetcode 788 | Super Simplified Explanation | Brute | Digit DPPragya Gupta · 19:24 · 641 views
LeetCode 788 | Rotated Digits | DP | JavaSleepy Cracker · 6:49 · 559 views
788. Rotated Digits | Leetcode Daily - PythonLeetcode Daily · 5:07 · 518 views
Rotated Digits | LeetCode 788 - Pythonimpoldev · 6:35 · 280 views
The problem
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, and8rotate to themselves,2and5rotate to each other (in this case they are rotated in a different direction, in other words,2or5gets mirrored),6and9rotate to each other, and- the rest of the numbers do not rotate to any other number and become invalid.
Given 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 <= 104
Approach overview
Problem 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 1: Direct Check Approach
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.
def rotatedDigits(n):
def isGoodNumber(x):
validDifferentDigitExists = False
while x > 0:
digit = x % 10
if digit in {3, 4, 7}:
return False
if digit in {2, 5, 6, 9}:
validDifferentDigitExists = True
x //= 10
return validDifferentDigitExists
count = 0
for i in range(1, n + 1):
if isGoodNumber(i):
count += 1
return count
# Example usage:
print(rotatedDigits(10))class Solution {
public int rotatedDigits(int n) {
int count = 0;
for (int i = 1; i <= n; i++) {
if (isGoodNumber(i)) count++;
}
return count;
}
private boolean isGoodNumber(int n) {
boolean validDifferentDigitExists = false;
while (n > 0) {
int digit = n % 10;
if (digit == 3 || digit == 4 || digit == 7) return false;
if (digit == 2 || digit == 5 || digit == 6 || digit == 9) validDifferentDigitExists = true;
n /= 10;
}
return validDifferentDigitExists;
}
public static void main(String[] args) {
Solution solution = new Solution();
System.out.println(solution.rotatedDigits(10));
}
}#include <iostream>
#include <unordered_set>
bool isGoodNumber(int n) {
bool validDifferentDigitExists = false;
while (n > 0) {
int digit = n % 10;
if (digit == 3 || digit == 4 || digit == 7) return false;
if (digit == 2 || digit == 5 || digit == 6 || digit == 9) validDifferentDigitExists = true;
n /= 10;
}
return validDifferentDigitExists;
}
int rotatedDigits(int n) {
int count = 0;
for (int i = 1; i <= n; ++i) {
if (isGoodNumber(i)) count++;
}
return count;
}
int main() {
int n = 10;
std::cout << rotatedDigits(n) << std::endl;
return 0;
}function rotatedDigits(n) {
function isGoodNumber(num) {
let validDifferentDigitExists = false;
while (num > 0) {
const digit = num % 10;
if ([3, 4, 7].includes(digit)) return false;
if ([2, 5, 6, 9].includes(digit)) validDifferentDigitExists = true;
num = Math.floor(num / 10);
}
return validDifferentDigitExists;
}
let count = 0;
for (let i = 1; i <= n; i++) {
if (isGoodNumber(i)) count++;
}
return count;
}
console.log(rotatedDigits(10));#include <stdio.h>
int isGoodNumber(int n) {
int validDifferentDigitExists = 0;
while (n > 0) {
int digit = n % 10;
if (digit == 3 || digit == 4 || digit == 7) return 0; // Not a valid digit
if (digit == 2 || digit == 5 || digit == 6 || digit == 9) validDifferentDigitExists = 1;
n /= 10;
}
return validDifferentDigitExists;
}
int rotatedDigits(int n) {
int count = 0;
for (int i = 1; i <= n; i++) {
if (isGoodNumber(i)) count++;
}
return count;
}
int main() {
int n = 10;
printf("%d\n", rotatedDigits(n));
return 0;
}using System;
public class Solution {
public int RotatedDigits(int n) {
int count = 0;
for (int i = 1; i <= n; i++) {
if (IsGoodNumber(i)) count++;
}
return count;
}
private bool IsGoodNumber(int n) {
bool validDifferentDigitExists = false;
while (n > 0) {
int digit = n % 10;
if (digit == 3 || digit == 4 || digit == 7) return false;
if (digit == 2 || digit == 5 || digit == 6 || digit == 9) validDifferentDigitExists = true;
n /= 10;
}
return validDifferentDigitExists;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.RotatedDigits(10));
}
}In Python, the solution evaluates each number's digits for validity and transformation powers. We count good numbers in a range using the isGoodNumber helper function.
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.
Approach 2: Digit-by-Digit Transformation Approach
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.
def rotatedDigits(n):
lookup = {0: 0, 1: 1, 2: 5, 3: -1, 4: -1, 5: 2, 6: 9, 7: -1, 8: 8, 9: 6}
count = 0
for i in range(1, n + 1):
x, transformed, power = i, 0, 1
while x > 0:
digit = x % 10
if lookup[digit] == -1:
transformed = -1
break
transformed = lookup[digit] * power + transformed
power *= 10
x //= 10
if transformed != -1 and transformed != i:
count += 1
return count
# Example usage:
print(rotatedDigits(10))class Solution {
private static final int[] rotationMap = {0, 1, 2, -1, -1, 5, 9, -1, 8, 6};
public int rotatedDigits(int n) {
int count = 0;
for (int i = 1; i <= n; i++) {
if (isGoodNumber(i)) {
count++;
}
}
return count;
}
private boolean isGoodNumber(int n) {
int transformed = 0, power = 1, original = n;
while (n > 0) {
int digit = n % 10;
if (rotationMap[digit] == -1) return false;
transformed = rotationMap[digit] * power + transformed;
power *= 10;
n /= 10;
}
return transformed != original;
}
public static void main(String[] args) {
Solution solution = new Solution();
int result = solution.rotatedDigits(10);
System.out.println(result);
}
}#include <iostream>
#include <vector>
int rotatedDigits(int n) {
std::vector<int> lookup = {0, 1, 2, -1, -1, 5, 9, -1, 8, 6};
int count = 0;
for (int i = 1; i <= n; ++i) {
int x = i, transformed = 0, power = 1;
while (x > 0) {
int digit = x % 10;
if (lookup[digit] == -1) {
transformed = -1;
break;
}
transformed = lookup[digit] * power + transformed;
power *= 10;
x /= 10;
}
if (transformed != -1 && transformed != i) {
count++;
}
}
return count;
}
int main() {
int n = 10;
std::cout << rotatedDigits(n) << std::endl;
return 0;
}function rotatedDigits(n) {
const lookup = {0: 0, 1: 1, 2: 5, 3: -1, 4: -1, 5: 2, 6: 9, 7: -1, 8: 8, 9: 6};
let count = 0;
for (let i = 1; i <= n; i++) {
let x = i, transformed = 0, power = 1;
while (x > 0) {
const digit = x % 10;
if (lookup[digit] === -1) {
transformed = -1;
break;
}
transformed = lookup[digit] * power + transformed;
power *= 10;
x = Math.floor(x / 10);
}
if (transformed !== -1 && transformed !== i) {
count++;
}
}
return count;
}
console.log(rotatedDigits(10));#include <stdio.h>
int validDigits[] = {0, 1, 2, -1, -1, 5, 9, -1, 8, 6};
int isGoodNumber(int n) {
int transformed = 0, power = 1, original = n;
while (n > 0) {
int digit = n % 10;
if (validDigits[digit] == -1) return 0; // invalid number
transformed = validDigits[digit] * power + transformed;
power *= 10;
n /= 10;
}
return transformed != original;
}
int rotatedDigits(int n) {
int count = 0;
for (int i = 1; i <= n; ++i) {
if (isGoodNumber(i)) {
count++;
}
}
return count;
}
int main() {
int n = 10;
printf("%d\n", rotatedDigits(n));
return 0;
}using System;
public class Solution {
public int RotatedDigits(int n) {
int[] rotationMap = {0, 1, 2, -1, -1, 5, 9, -1, 8, 6};
int count = 0;
for (int i = 1; i <= n; i++) {
int x = i, transformed = 0, power = 1;
while (x > 0) {
int digit = x % 10;
if (rotationMap[digit] == -1) {
transformed = -1;
break;
}
transformed = rotationMap[digit] * power + transformed;
power *= 10;
x /= 10;
}
if (transformed != -1 && transformed != i) {
count++;
}
}
return count;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.RotatedDigits(10));
}
}With Python, a dictionary is used for fast lookup of digit transformations, iterating over numbers to identify those which transform validly into a different number.
Time Complexity: O(n * d), since we check each digit of numbers from 1 to n.
Space Complexity: O(1), as only a constant-sized data structure is used.
Approach 3: Direct Enumeration
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:
function rotatedDigits(n: number): number {
const d: number[] = [0, 1, 5, -1, -1, 2, 9, -1, 8, 6];
const check = (x: number): boolean => {
let y = 0;
let t = x;
let k = 1;
while (t > 0) {
const v = t % 10;
if (d[v] === -1) {
return false;
}
y = d[v] * k + y;
k *= 10;
t = Math.floor(t / 10);
}
return x !== y;
};
return Array.from({ length: n }, (_, i) => i + 1).filter(check).length;
}func rotatedDigits(n int) int {
d := []int{0, 1, 5, -1, -1, 2, 9, -1, 8, 6}
check := func(x int) bool {
y, t := 0, x
k := 1
for ; t > 0; t /= 10 {
v := t % 10
if d[v] == -1 {
return false
}
y = d[v]*k + y
k *= 10
}
return x != y
}
ans := 0
for i := 1; i <= n; i++ {
if check(i) {
ans++
}
}
return ans
}Approach 4: Digit DP
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:
function rotatedDigits(n: number): number {
const s = n.toString();
const m = s.length;
const f: number[][] = Array.from({ length: m }, () => Array(2).fill(-1));
const dfs = (i: number, ok: number, limit: boolean): number => {
if (i >= m) {
return ok;
}
if (!limit && f[i][ok] !== -1) {
return f[i][ok];
}
const up = limit ? +s[i] : 9;
let ans = 0;
for (let j = 0; j <= up; ++j) {
if ([0, 1, 8].includes(j)) {
ans += dfs(i + 1, ok, limit && j === up);
} else if ([2, 5, 6, 9].includes(j)) {
ans += dfs(i + 1, 1, limit && j === up);
}
}
if (!limit) {
f[i][ok] = ans;
}
return ans;
};
return dfs(0, 0, true);
}func rotatedDigits(n int) int {
s := strconv.Itoa(n)
m := len(s)
f := make([][2]int, m)
for i := range f {
f[i] = [2]int{-1, -1}
}
var dfs func(i, ok int, limit bool) int
dfs = func(i, ok int, limit bool) int {
if i >= m {
return ok
}
if !limit && f[i][ok] != -1 {
return f[i][ok]
}
up := 9
if limit {
up = int(s[i] - '0')
}
ans := 0
for j := 0; j <= up; j++ {
if j == 0 || j == 1 || j == 8 {
ans += dfs(i+1, ok, limit && j == up)
} else if j == 2 || j == 5 || j == 6 || j == 9 {
ans += dfs(i+1, 1, limit && j == up)
}
}
if !limit {
f[i][ok] = ans
}
return ans
}
return dfs(0, 0, true)
}Complexity comparison
| 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), since we check each digit of numbers from 1 to n. |
| Direct Enumeration | – |
| Digit DP | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Rotated Digits easy or hard?
Rotated Digits is considered a medium-level problem. The base solution is simple digit validation, but recognizing the digit DP optimization requires stronger dynamic programming insight.
How to solve Rotated Digits in O(n)?
Most implementations run in O(n log n) because each number's digits must be inspected. However, digit DP can reduce the effective complexity to O(log n) by processing the digits of n and counting valid states rather than checking every integer.
What is the best approach for Rotated Digits?
The best practical approach is scanning numbers from 1 to n and validating digits. This Direct Check method runs in O(n log n) time and uses constant space. For deeper optimization, digit dynamic programming counts valid patterns in O(log n) time.
What data structure is used in Rotated Digits?
The problem mainly uses basic digit processing with arithmetic operations. Optimized solutions may use memoization tables or DP states when implementing digit dynamic programming to track valid rotations.
What is the time complexity of Rotated Digits?
The straightforward solution checks every number up to n and inspects its digits, resulting in O(n log n) time. A digit dynamic programming approach reduces the complexity to about O(log n) by counting valid digit combinations instead of iterating through all numbers.
Rotated Digits Python or Java solution approach?
Both Python and Java implementations typically iterate from 1 to n and validate digits using a mapping or conditional checks. The same logic applies across languages because the algorithm relies on simple digit extraction and rotation rules.
Is Rotated Digits asked at Google or Amazon interviews?
Rotated Digits appears in interview preparation sets and has been associated with companies like Google and Amazon in coding practice platforms. The problem tests digit manipulation, validation logic, and sometimes digit dynamic programming concepts.