Domain 1EasyCORE

Rotated Digits

The problem asks us to determine how many numbers between 1 and N (inclusive) are "good" after rotating each digit by 180 degrees. A number is considered "good" if it transforms into a valid number that is different from the original number. The digits 0, 1, and 8 rotate to themselves; 2 and 5 rotate to each other; 6 and 9 rotate to each other; while the rest (3, 4, 7) become invalid after rotation.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

788. Rotated Digits

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 57.5%


Problem Breakdown

The problem asks us to determine how many numbers between 1 and N (inclusive) are “good” after rotating each digit by 180 degrees. A number is considered “good” if it transforms into a valid number that is different from the original number. The digits 0, 1, and 8 rotate to themselves; 2 and 5 rotate to each other; 6 and 9 rotate to each other; while the rest (3, 4, 7) become invalid after rotation.

Inputs:

  • A positive integer N (1 ≤ N ≤ 10000).

Outputs:

  • An integer representing the count of “good” numbers between 1 and N.

Implicit Constraints/Edge Cases:

  • Single-digit numbers like 1, 8 are not considered good because they remain unchanged.
  • Numbers containing invalid digits (3, 4, 7) should be immediately disqualified.
  • The range is limited to 10000, so a brute-force approach might work but could be inefficient.

Intuition

A brute-force approach would involve checking each number from 1 to N individually. For each number, we’d convert it to a string and check if all its digits are valid after rotation. If they are, we’d then check if the rotated number is different from the original. This approach has a time complexity of O(N * D), where D is the average number of digits in the numbers between 1 and N.

However, this can be optimized by precomputing which digits are “good” (2, 5, 6, 9) and which are neutral (0, 1, 8). We can then use these classifications to quickly determine if a number is good without rotating each digit individually for every number.

Approach

  1. Classify Digits: Create two sets:

    • good_digits containing {2, 5, 6, 9} (digits that change after rotation).
    • neutral_digits containing {0, 1, 8} (digits that remain the same after rotation).
  2. Iterate Through Numbers: For each number from 1 to N:

    • Convert the number to a string.
    • Check if all digits are either in good_digits or neutral_digits.
    • If any digit is not in these sets, skip the number.
    • If the number contains at least one digit from good_digits, it is considered good.
  3. Count Good Numbers: Maintain a counter to keep track of how many numbers meet the criteria.

Complexity Analysis

  • Time Complexity: O(N * D), where N is the input number and D is the average number of digits in the numbers between 1 and N. Since D is constant (at most 5 for numbers up to 10000), this simplifies to O(N).
  • Space Complexity: O(1) for the additional space used by sets and counters.

Solution

def rotatedDigits(N: int) -> int:
    good_digits = {2, 5, 6, 9}
    neutral_digits = {0, 1, 8}
    
    def is_good_number(num):
        num_str = str(num)
        has_good_digit = False
        for digit in num_str:
            if int(digit) not in good_digits and int(digit) not in neutral_digits:
                return False
            if int(digit) in good_digits:
                has_good_digit = True
        return has_good_digit
    
    count = 0
    for i in range(1, N + 1):
        if is_good_number(i):
            count += 1
    
    return count

Edge Cases Handled

  • Single-digit numbers: Numbers like 1 and 8 are not considered good because they remain unchanged.
  • Numbers with invalid digits: Any number containing the digits 3, 4, or 7 is immediately disqualified.
  • Range limit: The solution efficiently handles the upper limit of N = 10000 without excessive computation.