1056. Confusing Number
Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 1
Acceptance rate: 47.0%
Problem Breakdown
The problem asks us to determine if a given number N is a “confusing number.” A confusing number is defined as one that, when rotated 180 degrees, becomes a different valid number. The digits 0, 1, 6, 8, and 9 can be rotated to form new digits (0, 1, 9, 8, 6 respectively), while the digits 2, 3, 4, 5, and 7 become invalid when rotated.
Inputs:
- A single integer
Nwhere0 <= N <= 10^9.
Outputs:
- A boolean value indicating whether
Nis a confusing number.
Implicit Constraints/Edge Cases:
- If
Ncontains any of the digits 2, 3, 4, 5, or 7, it should immediately return false. - Leading zeros in the rotated result are ignored (e.g., rotating 89 results in 68, not 068).
- Single-digit numbers like 11 are not confusing because they remain the same after rotation.
Intuition
The brute-force approach would involve checking each digit of N to see if it is valid for rotation and then constructing the rotated number. However, this approach can be inefficient in terms of space complexity as it requires storing intermediate results.
A better approach involves reversing the digits of N, rotating them as we go, and comparing the final result with the original number. This way, we avoid unnecessary storage and directly compute the rotated value.
Approach
- Mapping Digits: Create a dictionary to map each valid digit to its rotated counterpart.
- Reversing and Rotating: Initialize an empty list to store the digits of the rotated number. Iterate through each digit of
N, check if it is valid for rotation, and append its rotated counterpart to the list. - Comparison: Convert the list of rotated digits back into a number and compare it with the original number. If they are different, return true; otherwise, return false.
Complexity Analysis
- Time Complexity: O(log N), where N is the input number. This is because we iterate through each digit of
N. - Space Complexity: O(1) for storing the rotated digits and other variables.
Solution
def confusingNumber(N: int) -> bool:
# Mapping of valid digits to their rotated counterparts
rotation_map = {0: 0, 1: 1, 6: 9, 8: 8, 9: 6}
original_number = N
rotated_number = 0
while N > 0:
digit = N % 10
if digit not in rotation_map:
return False
rotated_digit = rotation_map[digit]
rotated_number = rotated_number * 10 + rotated_digit
N //= 10
# Check if the original number is different from the rotated number
return rotated_number != original_number
Edge Cases Handled
- Single-digit numbers: Numbers like 11 are not confusing because they remain the same after rotation.
- Numbers with invalid digits: If
Ncontains any of the digits 2, 3, 4, 5, or 7, the function returns false immediately. - Leading zeros in rotated result: The algorithm naturally handles this by ignoring leading zeros since we construct the rotated number directly.