algoadvance

  1. Rotated Digits

X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from X. Each digit must be rotated, and the result must be a valid number.

Each digit must be rotated as follows:

A number is valid if each digit can be rotated to form another valid digit. A number is different if it does not include any of {3, 4, 7}.

Given a positive integer N, how many numbers X from 1 to N are good?

Clarifying Questions

  1. Edge Cases:
    • What if N is 0 or 1? We should handle small values of N correctly.
  2. Constraints:
    • Positive integer N (1 <= N <= 10^4). We need to ensure the solution scales well within this range.

Strategy

  1. Identify Good and Bad Digits:
    • Good digits: {0, 1, 8, 2, 5, 6, 9}
    • Bad digits: {3, 4, 7}
  2. Check Each Number:
    • Iterate through each number from 1 to N.
    • For each number, check if it contains only good digits.
    • Additionally, ensure it contains at least one of the “rotatable” digits that change when rotated (i.e., 2, 5, 6, 9) to confirm it becomes a different number after rotation.
  3. Count the Good Numbers:
    • Use a counter to keep track of numbers that meet the criteria described above.

Code

def rotatedDigits(N: int) -> int:
    def is_good(number):
        valid = {'0', '1', '8', '2', '5', '6', '9'}
        changes = {'2', '5', '6', '9'}
        num_str = str(number)
        
        if any(digit in '347' for digit in num_str):
            return False
        
        return any(digit in changes for digit in num_str)

    count = 0
    for num in range(1, N + 1):
        if is_good(num):
            count += 1
            
    return count

# Example usage:
print(rotatedDigits(10))  # Output: 4

Explanation

  1. Helper Function (is_good):
    • number converted to string form allows easy iteration digit by digit.
    • We check if any digit is in the set {‘3’, ‘4’, ‘7’} which is invalid.
    • Ensure at least one digit is in the set {‘2’, ‘5’, ‘6’, ‘9’} ensuring it changes upon rotation.
  2. Main Function (rotatedDigits):
    • Iterate through the range 1 to N.
    • Use the helper function is_good to check each number.
    • Count and return the total numbers that meet the criteria.

Time Complexity

Try our interview co-pilot at AlgoAdvance.com