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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Confusing Number II

Number: 1077

Difficulty: Hard

Paid? Yes

Companies: Google

Problem Description

Given a positive integer n, count the number of confusing numbers in the range [1, n]. A confusing number is defined as a number that when rotated 180 degrees becomes another valid number that is different from the original. The valid rotations are: 0 → 0, 1 → 1, 6 → 9, 8 → 8, and 9 → 6. Digits 2, 3, 4, 5, and 7 are not valid after rotation. Note that any leading zeros after rotation are ignored.

Key Insights

  • Only use the digits 0, 1, 6, 8, and 9 to build the candidate numbers.
  • Use backtracking (or DFS) to generate numbers less than or equal to n.
  • For any generated number, check if its rotated version (using the mapping) is different from the original.
  • Avoid numbers with leading zeros.
  • The problem is effectively a DFS/backtracking search with a pruning condition (number > n).

Space and Time Complexity

Time Complexity: O(5^L) where L is the maximum number of digits in n; since n can be up to 10^9, L is at most 10.
Space Complexity: O(L) due to recursion stack.

Solution

Use a depth-first search to recursively build numbers using the allowed digits (0, 1, 6, 8, 9).
For each constructed number (ignoring 0 as the starting number), check whether it is a confusing number by rotating it using a mapping (0→0, 1→1, 6→9, 8→8, 9→6) and comparing it to the original.
If they differ, increment a counter.
Prune the DFS branch if the generated number exceeds n.
This approach leverages backtracking to ensure all valid combinations are examined without explicitly checking every number from 1 to n.

Code Solutions

# Python solution for Confusing Number II

def confusingNumberII(n: int) -> int:
    # Mapping for valid rotations
    rotation_map = {0: 0, 1: 1, 6: 9, 8: 8, 9: 6}
    
    count = 0  # Global counter for confusing numbers
    
    def is_confusing(num: int) -> bool:
        original = num
        rotated = 0
        # Generate rotated number
        while num:
            digit = num % 10
            rotated = rotated * 10 + rotation_map[digit]
            num //= 10
        # Check if rotated number is different from original
        return rotated != original

    def dfs(current: int):
        nonlocal count
        # If current number is within bounds and not 0 (we don't count 0)
        if current != 0 and current <= n:
            if is_confusing(current):
                count += 1
        # List of valid digits sorted in ascending order
        for digit in [0, 1, 6, 8, 9]:
            new_number = current * 10 + digit
            # If the generated number exceeds n, no need to proceed in this branch
            if new_number > n:
                continue
            # Avoid numbers with leading zero
            if current == 0 and digit == 0:
                continue
            dfs(new_number)

    dfs(0)
    return count

# Example usage:
#print(confusingNumberII(20))  # Expected output: 6
← Back to All Questions