# 1088. Confusing Number II

We can rotate digits by 180 degrees to form new digits. When 0, 1, 6, 8, 9 are rotated 180 degrees, they become 0, 1, 9, 8, 6 respectively. When 2, 3, 4, 5 and 7 are rotated 180 degrees, they become invalid.

A *confusing number* is a number that when rotated 180 degrees becomes a **different** number with each digit valid.(Note that the rotated number can be greater than the original number.)

Given a positive integer `N`, return the number of confusing numbers between `1` and `N` inclusive.

**Example 1:**

```
Input: 20
Output: 6
Explanation: 
The confusing numbers are [6,9,10,16,18,19].
6 converts to 9.
9 converts to 6.
10 converts to 01 which is just 1.
16 converts to 91.
18 converts to 81.
19 converts to 61.
```

**Example 2:**

```
Input: 100
Output: 19
Explanation: 
The confusing numbers are [6,9,10,16,18,19,60,61,66,68,80,81,86,89,90,91,98,99,100].
```

**Note:**

1. `1 <= N <= 10^9`

```cpp
// Naive Recursion
void helper(long num, long rotate_num, const int& N, unordered_map<int, int>& rotate_mp, long base, int& res) {
    if (num != rotate_num) ++res;
    for (const auto& e : rotate_mp) {
        if (!e.first && !num) continue;
        long new_num = num * 10 + e.first;
        if (new_num > N) continue;
        helper(new_num, rotate_mp[e.first] * base + rotate_num, N, rotate_mp, base * 10, res);
    }
} 
int confusingNumberII(int N) {
    unordered_map<int, int> rotate_mp;
    rotate_mp[0] = 0;
    rotate_mp[1] = 1;
    rotate_mp[6] = 9;
    rotate_mp[8] = 8;
    rotate_mp[9] = 6;
    int res = 0;
    helper(0, 0, N, rotate_mp, 1, res);
    return res;
}
```

```cpp
// Count numbers with digits in "01689" from 0 to s
int findAll(const string& s) {
    const string digits = "01689";
    if (s.length() == 1) {
        int res = 0;
        for (char c : digits) {
            if (c <= s[0]) ++res;
        }
        return res;
    } else {
        int smaller = 0;
        for (char c : digits) {
            if (c < s[0]) ++smaller;
        }
        int res = smaller * powl(5, s.length() - 1);
        if (digits.find(s[0]) != string::npos) res += findAll(s.substr(1));
        return res;
    }
}
int confusingNumberII(int N) { // time: O(5^len(num)); space: O(len(num))
    const string num = to_string(N);
    const vector<string> rotate_mp({"00", "11", "88", "69", "96"});
    const int num_len = num.length();
    vector<vector<string> > level(num_len + 1);
    level[0] = {""};
    int strobogrammatic_number = 0;
    for (int len = 1; len <= num_len; ++len) {
        if (len == 1) {
            level[len] = {"0", "1", "8"};
        } else {
            for (const string& middle : level[len - 2]) {
                for (const string& pair : rotate_mp) {
                    level[len].push_back(pair[0] + middle + pair[1]);
                }
            }
        }
        for (const string& t : level[len]) {
            if (len > 1 && t[0] == '0') continue;
            long n = stol(t);
            if (n <= N) ++strobogrammatic_number;
        }
    }
    // (# of confusing numbers = # of numbers with digits "01689" <= num) - (# of strobogrammatic numbers)
    return findAll(num) - strobogrammatic_number; 
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/math/1088.-confusing-number-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.