# 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.

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`

``````class Solution {
public:
int confusingNumberII(int N) {
int res = 0;
unordered_map<int, int> m{{0, 0}, {1, 1}, {6, 9}, {8, 8}, {9, 6}};
helper(N, 0, m, res);
return res;
}
void helper(int N, long cur, unordered_map<int, int>& m, int& res) {
if (isConfusingNum(cur, m)) ++res;
for (auto a : m) {
if (cur * 10 + a.first <= N && cur * 10 + a.first != 0) {
helper(N, cur * 10 + a.first, m, res);
}
}
}
bool isConfusingNum(long num, unordered_map<int, int>& m) {
long oldNum = num, res = 0;
while (num > 0) {
if (m.count(num % 10)) return false;
res = res * 10 + m[num % 10];
num /= 10;
}
return res != oldNum;
}
};
``````

``````class Solution {
public:
int confusingNumberII(int N) {
int res = 0;
map<int, int> m{{0, 0}, {1, 1}, {6, 9}, {8, 8}, {9, 6}};
vector<int> vec{0};
bool found = false;
while (!found) {
vector<int> t;
for (int num : vec) {
for (auto a : m) {
int cur = num * 10 + a.first;
if (cur > N) {
found = true; break;
}
if (cur != 0) t.push_back(cur);
if (isConfusingNum(cur, m)) ++res;
}
if (found) break;
}
vec = t;
}
return res;
}
bool isConfusingNum(int num, map<int, int>& m) {
int oldNum = num, res = 0;
while (num > 0) {
if (!m.count(num % 10)) return false;
res = res * 10 + m[num % 10];
num /= 10;
}
return res != oldNum;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1088

Confusing Number

https://leetcode.com/problems/confusing-number-ii/

https://leetcode.com/problems/confusing-number-ii/discuss/313407/Backtracking-and-Iterative-Solution-in-Java

https://leetcode.com/problems/confusing-number-ii/discuss/446589/Easy-to-understand-Java-backtracking-solution-covers-edge-case

https://leetcode.com/problems/confusing-number-ii/discuss/392786/Confusing-number-Total-number-Strobogrammatic-number-(Java-1ms)

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation