LeetCode 1088: Confusing Number II Solution

Master LeetCode problem 1088 (Confusing Number II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1088. Confusing Number II

Hard

Math Backtracking

Problem Explanation

Explanation:

This problem asks us to count the numbers that are confusing. A number is considered confusing if, when rotated 180 degrees, it becomes a different number with each digit valid. For example, 0, 1, 6, 8, 9 are valid digits since their rotations are also valid, while 2, 3, 4, 5, 7 are not valid as they become different digits when rotated.

To solve this problem, we can use backtracking to generate all possible confusing numbers of a given length. We start by initializing the count to 0 and then recursively generate all possible confusing numbers by trying each digit at each position, checking if the number is valid, and incrementing the count accordingly.

Finally, we return the count as the result.

: :

Solution Code

class Solution {
    int count = 0;
    
    public int confusingNumberII(int N) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 0);
        map.put(1, 1);
        map.put(6, 9);
        map.put(8, 8);
        map.put(9, 6);
        
        backtrack(N, 0, map);
        
        return count;
    }
    
    private void backtrack(int N, long current, Map<Integer, Integer> map) {
        if (isConfusing(current)) {
            count++;
        }
        
        for (int key : map.keySet()) {
            if (current * 10 + key <= N && current * 10 + key != 0) {
                backtrack(N, current * 10 + key, map);
            }
        }
    }
    
    private boolean isConfusing(long num) {
        long original = num;
        long confusing = 0;
        
        while (num > 0) {
            confusing = confusing * 10 + map.get((int)(num % 10));
            num /= 10;
        }
        
        return confusing != original;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1088 (Confusing Number II)?

This page provides optimized solutions for LeetCode problem 1088 (Confusing Number II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1088 (Confusing Number II)?

The time complexity for LeetCode 1088 (Confusing Number II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1088 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1088 in Java, C++, or Python.

Back to LeetCode Solutions