Problem Description

You need to find how many "good" integers exist in the range from 1 to n.

An integer is considered good if it meets two conditions:

1. After rotating each of its digits by 180 degrees, the result is still a valid number
2. The rotated number must be different from the original number

When a digit is rotated by 180 degrees:

• 0, 1, and 8 remain the same (0→0, 1→1, 8→8)
• 2 and 5 swap with each other (2→5, 5→2)
• 6 and 9 swap with each other (6→9, 9→6)
• All other digits (3, 4, 7) become invalid after rotation

For a number to remain valid after rotation, it can only contain the digits 0, 1, 2, 5, 6, 8, 9. If it contains any other digit, the rotation produces an invalid result.

For example:

• 69 is a good number because rotating it gives 96, which is valid and different from 69
• 11 is NOT a good number because rotating it gives 11, which is the same as the original
• 34 is NOT a good number because it contains 3 and 4, which don't have valid rotations

Given an integer n, return the count of all good integers in the range [1, n].

Intuition

The most straightforward way to solve this problem is to check each number from 1 to n individually to see if it's a "good" number.

To determine if a number is good, we need to:

1. Check if all its digits are valid (can be rotated)
2. Build the rotated version of the number
3. Compare the rotated version with the original

The key insight is to create a mapping that tells us what each digit becomes after rotation. We can use an array d where d[i] represents what digit i becomes after a 180-degree rotation:

• d[0] = 0 (0 stays 0)
• d[1] = 1 (1 stays 1)
• d[2] = 5 (2 becomes 5)
• d[5] = 2 (5 becomes 2)
• d[6] = 9 (6 becomes 9)
• d[8] = 8 (8 stays 8)
• d[9] = 6 (9 becomes 6)
• For invalid digits (3, 4, 7), we set d[i] = -1

To check a number x, we process it digit by digit from right to left:

1. Extract each digit using modulo operation (t % 10)
2. If we encounter an invalid digit (where d[v] == -1), the number cannot be rotated properly
3. Otherwise, we build the rotated number y by adding the rotated digit at the appropriate position
4. After processing all digits, if x != y, then x is a good number

The reason we build the rotated number from right to left is that it allows us to construct y in the correct order by multiplying each rotated digit by the appropriate power of 10.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The solution uses direct enumeration to check each number from 1 to n and count how many are "good" numbers.

Data Structure:

• An array d of length 10 that maps each digit to its rotated counterpart:

  d = [0, 1, 5, -1, -1, 2, 9, -1, 8, 6]

  Where d[i] represents what digit i becomes after rotation. Invalid digits are marked with -1.

Algorithm Implementation:

1. Main Function (rotatedDigits):

   • Iterate through all numbers from 1 to n
   • For each number i, call check(i) to determine if it's good
   • Sum up all the good numbers using sum(check(i) for i in range(1, n + 1))

2. Check Function (check): The function determines if a number x is good by:

   a. Initialize variables:

   • y = 0: stores the rotated number
   • t = x: temporary variable for processing digits
   • k = 1: position multiplier (powers of 10)

   b. Process each digit from right to left:

   while t:
       v = t % 10  # Extract rightmost digit
       if d[v] == -1:  # Check if digit is invalid
           return False
       y = d[v] * k + y  # Build rotated number
       k *= 10  # Move to next position
       t //= 10  # Remove processed digit

   c. Final validation:

   • Return x != y to ensure the rotated number is different from the original

Example walkthrough for x = 25:

• First iteration: v = 5, d[5] = 2, y = 2 * 1 + 0 = 2, k = 10
• Second iteration: v = 2, d[2] = 5, y = 5 * 10 + 2 = 52, k = 100
• Result: y = 52, which is different from x = 25, so it's a good number

Time Complexity: O(n × log n) where n is the input number. We check n numbers, and for each number, we process O(log n) digits.

Space Complexity: O(1) as we only use a fixed-size array and a few variables.

Example Walkthrough

Let's walk through finding all good numbers from 1 to 10.

Setup: We have our rotation mapping array: d = [0, 1, 5, -1, -1, 2, 9, -1, 8, 6]

Checking each number:

1. n = 1:

   • Extract digit: 1 → rotates to 1
   • Rotated number: 1
   • Is 1 ≠ 1? No → NOT good

2. n = 2:

   • Extract digit: 2 → rotates to 5
   • Rotated number: 5
   • Is 2 ≠ 5? Yes → GOOD ✓

3. n = 3:

   • Extract digit: 3 → d[3] = -1 (invalid)
   • Cannot rotate → NOT good

4. n = 4:

   • Extract digit: 4 → d[4] = -1 (invalid)
   • Cannot rotate → NOT good

5. n = 5:

   • Extract digit: 5 → rotates to 2
   • Rotated number: 2
   • Is 5 ≠ 2? Yes → GOOD ✓

6. n = 6:

   • Extract digit: 6 → rotates to 9
   • Rotated number: 9
   • Is 6 ≠ 9? Yes → GOOD ✓

7. n = 7:

   • Extract digit: 7 → d[7] = -1 (invalid)
   • Cannot rotate → NOT good

8. n = 8:

   • Extract digit: 8 → rotates to 8
   • Rotated number: 8
   • Is 8 ≠ 8? No → NOT good

9. n = 9:

   • Extract digit: 9 → rotates to 6
   • Rotated number: 6
   • Is 9 ≠ 6? Yes → GOOD ✓

10. n = 10:

    • First digit: 0 → rotates to 0, y = 0
    • Second digit: 1 → rotates to 1, y = 1 × 10 + 0 = 10
    • Rotated number: 10
    • Is 10 ≠ 10? No → NOT good

Result: Good numbers in range [1, 10] are: 2, 5, 6, 9 Count: 4

Detailed trace for n = 25:

• Initialize: y = 0, t = 25, k = 1
• Iteration 1:
  • v = 25 % 10 = 5
  • d[5] = 2 (valid)
  • y = 2 × 1 + 0 = 2
  • k = 10, t = 2
• Iteration 2:
  • v = 2 % 10 = 2
  • d[2] = 5 (valid)
  • y = 5 × 10 + 2 = 52
  • k = 100, t = 0
• Final check: 25 ≠ 52? Yes → GOOD ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(n * log(n))

The main function iterates through all numbers from 1 to n, which gives us O(n) iterations. For each number i, the check function is called, which processes each digit of the number. The number of digits in a number i is O(log(i)), and in the worst case when i = n, this becomes O(log(n)). Therefore, the overall time complexity is O(n * log(n)).

Space Complexity: O(1)

The space complexity is constant because:

• The dictionary d is a fixed-size array of 10 elements, which takes O(1) space
• The check function uses only a fixed number of variables (y, t, k, v) regardless of input size
• No recursive calls are made, so there's no additional stack space usage
• The sum operation uses constant extra space for accumulation

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Building the Rotated Number

A common mistake is building the rotated number in the wrong order. When processing digits from right to left, developers might accidentally reverse the number or apply rotations incorrectly.

Incorrect approach:

# Wrong: This reverses the number while rotating
rotated = 0
while temp:
    digit = temp % 10
    rotated = rotated * 10 + rotation_map[digit]  # This reverses!
    temp //= 10

Correct approach:

# Correct: Maintains digit positions
rotated = 0
place_value = 1
while temp:
    digit = temp % 10
    rotated = rotation_map[digit] * place_value + rotated
    place_value *= 10
    temp //= 10

2. Forgetting to Check for Invalid Digits

Some developers might assume all digits can be rotated and forget to handle invalid cases (3, 4, 7).

Incorrect approach:

# Wrong: Assumes all digits are valid
rotation_map = [0, 1, 5, 0, 0, 2, 9, 0, 8, 6]  # Using 0 for invalid digits
# This would incorrectly process numbers like 34 as valid

Correct approach:

# Correct: Explicitly mark invalid digits
rotation_map = [0, 1, 5, -1, -1, 2, 9, -1, 8, 6]
if rotation_map[digit] == -1:
    return False

3. Missing the "Different Number" Requirement

A critical mistake is forgetting that good numbers must be different after rotation. Numbers like 11, 88, or 181 rotate to themselves and should NOT be counted.

Incorrect approach:

def is_good_number(number):
    # Check only if rotation is valid, not if it's different
    while temp:
        if rotation_map[digit] == -1:
            return False
        # ... build rotated number
    return True  # Wrong: doesn't check if number changed

Correct approach:

def is_good_number(number):
    # ... build rotated number
    return number != rotated_number  # Must be different!

4. Off-by-One Error in Range

Forgetting to include n in the range or starting from 0 instead of 1.

Incorrect approaches:

# Wrong: Excludes n
sum(is_good_number(i) for i in range(1, n))

# Wrong: Includes 0 (which isn't in the problem range)
sum(is_good_number(i) for i in range(0, n + 1))

Correct approach:

# Correct: Range [1, n] inclusive
sum(is_good_number(i) for i in range(1, n + 1))

5. Integer Overflow in Other Languages

While not an issue in Python, languages like C++ or Java might face integer overflow when building large rotated numbers. Always consider the constraints and use appropriate data types.

Solution for other languages:

• Use long long in C++ or long in Java when necessary
• Check problem constraints to ensure the rotated number fits within integer limits