Confusing Number II Solution in Python

Explore More Solutions

Problem Description

Ah, the Confusing Number II problem! It’s like trying to find your way through a maze while wearing a blindfold and spinning in circles. The task is to count how many confusing numbers exist up to a given number n. A confusing number is one that, when rotated 180 degrees, becomes a different number. For example, the number 6 becomes 9, and 9 becomes 6. But don’t worry, we’re not talking about your confusing ex; we’re talking about numbers that can be rotated and still make sense (sort of).

Imagine you’re at a party, and you see someone who looks like your friend but is actually a stranger. That’s what confusing numbers are like! They look familiar but are entirely different when you give them a little twist.

Code Solution


class Solution:
    def confusingNumberII(self, n: int) -> int:
        digitToRotated = [(0, 0), (1, 1), (6, 9), (8, 8), (9, 6)]

        def dfs(num: int, rotatedNum: int, unit: int) -> int:
            ans = 0 if num == rotatedNum else 1
            # Add one more digit
            for digit, rotated in digitToRotated:
                if digit == 0 and num == 0:
                    continue
                nextNum = num * 10 + digit
                if nextNum > n:
                    break
                ans += dfs(nextNum, rotated * unit + rotatedNum, unit * 10)
            return ans

        return dfs(0, 0, 1)

Approach Explanation

The code uses a depth-first search (DFS) approach to explore all possible numbers that can be formed with the digits that can be rotated. It maintains a mapping of digits to their rotated counterparts and recursively builds numbers while checking if they are confusing. If a number is different from its rotated version, it counts it as a confusing number.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(4^d)
Space Complexity	O(d)

Real-World Example

Think of a confusing number like a magician’s trick. You see a number, and when it’s flipped, it transforms into something else entirely. For instance, if you have a number like 69, it’s like a magician pulling a rabbit out of a hat—surprising and confusing! The task is to count how many such magical transformations exist up to a certain number n.