Code Implementation

class Solution:
    def confusingNumber(self, n: int) -> bool:
        rotate = {0:0, 1:1, 6:9, 8:8, 9:6}
        original = n
        rotated = 0
        while n > 0:
            digit = n % 10
            if digit not in rotate:
                return False
            rotated = rotated * 10 + rotate[digit]
            n //= 10
        return rotated != original
      

class Solution {
public:
    bool confusingNumber(int n) {
        unordered_map<int, int> rotate = {{0,0}, {1,1}, {6,9}, {8,8}, {9,6}};
        int original = n, rotated = 0;
        while (n > 0) {
            int digit = n % 10;
            if (rotate.find(digit) == rotate.end())
                return false;
            rotated = rotated * 10 + rotate[digit];
            n /= 10;
        }
        return rotated != original;
    }
};
      

class Solution {
    public boolean confusingNumber(int n) {
        Map<Integer, Integer> rotate = new HashMap<>();
        rotate.put(0, 0);
        rotate.put(1, 1);
        rotate.put(6, 9);
        rotate.put(8, 8);
        rotate.put(9, 6);
        int original = n;
        int rotated = 0;
        while (n > 0) {
            int digit = n % 10;
            if (!rotate.containsKey(digit)) {
                return false;
            }
            rotated = rotated * 10 + rotate.get(digit);
            n /= 10;
        }
        return rotated != original;
    }
}
      

var confusingNumber = function(n) {
    const rotate = {0:0, 1:1, 6:9, 8:8, 9:6};
    let original = n;
    let rotated = 0;
    while (n > 0) {
        let digit = n % 10;
        if (!(digit in rotate)) return false;
        rotated = rotated * 10 + rotate[digit];
        n = Math.floor(n / 10);
    }
    return rotated !== original;
};
      

Problem Description

Given an integer n, determine whether it is a "confusing number." A confusing number is a number that, when rotated 180 degrees, becomes a different valid number. Each digit must remain valid after rotation, according to the following rules:

• 0, 1, 6, 8, and 9 are valid digits when rotated.
• 2, 3, 4, 5, and 7 are invalid digits when rotated (the result is not a digit).
• When rotated, 6 becomes 9, and 9 becomes 6. 0, 1, and 8 remain the same.

The function should return True if n is a confusing number (i.e., it becomes a different number after rotation), and False otherwise.

Constraints: Each digit of n must be valid after rotation. If any digit is invalid, the number is not confusing.

Thought Process

Let's break down the problem. We need to check if a number, when rotated 180 degrees, is both valid and different from the original. First, we need a way to check if each digit is valid after rotation. Then, we need to compute the rotated number and compare it with the original.

A brute-force approach would be to convert the number to a string, reverse it, rotate each digit, and then compare. However, we can optimize by processing digits from right to left, directly building the rotated number. If we find any invalid digit in the process, we can stop early and return False.

We use a mapping for digit rotation and process the number digit by digit, which is efficient and avoids unnecessary string operations.

Solution Approach

Here's a step-by-step guide to solving the problem:

1. Define Rotation Mapping: Create a mapping for each valid digit to its rotated value:
   • 0 → 0
   • 1 → 1
   • 6 → 9
   • 8 → 8
   • 9 → 6
2. Iterate Over Digits: For each digit (from right to left), check if it is in the mapping. If not, return False immediately.
3. Build Rotated Number: Multiply the current rotated number by 10 and add the rotated digit. This effectively reverses the number and applies the rotation at the same time.
4. Compare: After processing all digits, compare the rotated number to the original number.
   • If they are different, return True (it's a confusing number).
   • If they are the same, return False (it's not confusing).

We use a hash map (dictionary) for O(1) digit lookup and avoid converting the number to a string, making the solution efficient.

Example Walkthrough

Let's walk through the process with n = 6:

• Original number: 6
• Process digit 6: valid, rotates to 9
• Build rotated number: 0 * 10 + 9 = 9
• No more digits left
• Rotated number is 9, which is different from 6
• Return True (6 is a confusing number)

Another example, n = 11:

• Process digit 1: valid, rotates to 1
• Process digit 1: valid, rotates to 1
• Build rotated number: 1 * 10 + 1 = 11
• Rotated number is 11, which is the same as the original
• Return False (11 is not a confusing number)

Time and Space Complexity

Brute-force Approach:

• Time Complexity: O(d), where d is the number of digits (since we process each digit once)
• Space Complexity: O(1), as we only use a few variables and a fixed-size mapping

• Time Complexity: O(d), same as above
• Space Complexity: O(1), as the mapping is constant size and no extra space is used per input size

The approach is already optimal for this problem.

Summary

To determine if a number is confusing, we rotate each digit using a predefined mapping, build the rotated number, and compare it to the original. If any digit is invalid, we can stop early. The solution is efficient, using only constant extra space and linear time in the number of digits. The key insight is to process digits in reverse order while rotating, allowing us to avoid string manipulation and extra storage.