LeetCode Solutions Blog

Confusing Number

Number: 1069

Difficulty: Easy

Paid? Yes

Companies: Google

Problem Description

Determine if an integer n is a confusing number. A confusing number, when rotated 180 degrees, forms a valid number that is different from n. The rotation rules are as follows: 0->0, 1->1, 6->9, 8->8, 9->6. If any digit in n is invalid upon rotation (i.e., 2,3,4,5,7), the number is not confusing.

Key Insights

Use a mapping dictionary for valid rotations: {0:0, 1:1, 6:9, 8:8, 9:6}.
Process the digits of n from right to left to form the rotated number.
If any digit is not present in the mapping, the number is instantly not confusing.
Compare the rotated number with the original number to check if they are different.

Space and Time Complexity

Time Complexity: O(d), where d is the number of digits in n (approximately O(log n)). Space Complexity: O(d), needed to store the rotated number string.

Solution

The approach is to convert the number to a string and iterate through it in reverse. For each digit, check if it is valid using the predefined mapping. If it is, append its rotated counterpart to a new string. After processing, convert the rotated string to an integer (ignoring any leading zeros). Finally, compare the rotated number to the original number. If they are different, the number is confusing.

Code Solutions

# Define the mapping for valid rotations
def is_confusing_number(n: int) -> bool:
    rotation_map = {'0': '0', '1': '1', '6': '9', '8': '8', '9': '6'}
    
    # Convert the number to a string to process each digit
    original_str = str(n)
    rotated_str = ""
    
    # Process each digit in reverse order to simulate 180 degree rotation
    for digit in reversed(original_str):
        # If digit is not valid for rotation, return false immediately
        if digit not in rotation_map:
            return False
        # Append the rotated digit to the rotated string
        rotated_str += rotation_map[digit]
    
    # Convert rotated string to an integer (leading zeros are ignored)
    rotated_num = int(rotated_str)
    
    # The number is confusing if the rotated number is different from the original number
    return rotated_num != n

# Example usage:
print(is_confusing_number(6))  # Expected output: True
print(is_confusing_number(89)) # Expected output: True
print(is_confusing_number(11)) # Expected output: False