We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Rotated Digits

Number: 804

Difficulty: Medium

Paid? No

Companies: Arista Networks, Google, Uber

Problem Description

Determine the count of numbers in the range [1, n] that become a valid number and change value after each digit is rotated by 180 degrees. Only digits 0, 1, 8 remain unchanged, while 2, 5 and 6, 9 swap with each other; digits 3, 4, and 7 are invalid after rotation.

Key Insights

  • A valid rotated number must only use the digits 0, 1, 8, 2, 5, 6, and 9.
  • A number is "good" if it contains at least one digit (2, 5, 6, or 9) that changes upon rotation.
  • If any digit in the number is 3, 4, or 7, the entire number becomes invalid.
  • Iterating through each number from 1 to n and checking the validity and difference after rotation works efficiently given the constraints.

Space and Time Complexity

Time Complexity: O(n * d) where d is the number of digits in the number (in worst case, d is small due to n ≤ 10⁴).
Space Complexity: O(1)

Solution

The approach involves iterating from 1 to n and checking each digit in the number. A mapping is used to convert each digit to its rotated counterpart. If a digit is not present in the mapping (i.e., it is 3, 4, or 7), the number is discarded immediately. If the rotated number differs from the original, the number is counted as "good". This method leverages simple string operations or arithmetic digit extraction to perform the check.

Code Solutions

def rotatedDigits(n):
    # Mapping for each digit to its rotated counterpart.
    rotate_map = {'0': '0', '1': '1', '8': '8', '2': '5', '5': '2', '6': '9', '9': '6'}
    count = 0
    # Iterate through each number from 1 to n inclusive.
    for number in range(1, n + 1):
        num_str = str(number)
        rotated = []
        valid = True
        different = False
        # Check each digit in the current number.
        for ch in num_str:
            if ch not in rotate_map:
                valid = False
                break
            rotated_digit = rotate_map[ch]
            rotated.append(rotated_digit)
            if rotated_digit != ch:
                different = True
        if valid and different:
            count += 1
    return count

# Example test
print(rotatedDigits(10))  # Expected output: 4
← Back to All Questions