How do you solve Rotated Digits on LeetCode?

Rotated Digits (LeetCode #788) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Good digits include 2, 5, 6, 9; invalid digits include 3, 4, 7.

What is the brute force solution for Rotated Digits?

The brute force approach for Rotated Digits is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each number from 1 to n, rotating its digits and verifying if the rotated number is different and valid. This is straightforward but inefficient for larger values of n. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Rotated Digits?

Rotated Digits uses the following concepts: Math, Dynamic Programming. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Rotated Digits?

Clarify the rotation rules before starting. Discuss edge cases, like single-digit numbers. Optimize your solution after the brute force approach.

What are common mistakes when solving Rotated Digits?

Not checking for invalid digits properly. Confusing valid rotations with good numbers.

#788

Rotated Digits

Medium

MathDynamic ProgrammingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution leverages pre-computed valid rotations and counts good numbers in a single pass. This is efficient and avoids redundant checks.

⚙️

Algorithm

6 steps

1Step 1: Create a set of valid digits and a set of good digits.
2Step 2: Initialize a counter to zero.
3Step 3: Loop through each number from 1 to n.
4Step 4: For each number, check if it contains any invalid digits.
5Step 5: If it contains only valid digits, check if it contains at least one good digit.
6Step 6: Increment the counter if the number is good.

solution.py10 lines

1def rotatedDigits(n):
2    good_digits = {'2', '5', '6', '9'}
3    valid_digits = {'0', '1', '8', '2', '5', '6', '9'}
4    count = 0
5    for i in range(1, n + 1):
6        s = str(i)
7        if all(d in valid_digits for d in s):
8            if any(d in good_digits for d in s):
9                count += 1
10    return count

ℹ

Complexity note: The time complexity is O(n) because we only loop through the numbers once and check each digit, which is efficient. The space complexity is O(1) as we use a fixed amount of space for the sets.

1Good digits include 2, 5, 6, 9; invalid digits include 3, 4, 7.
2A number is good if it contains at least one good digit and no invalid digits.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.