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 <= N <= 10^9
// 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;
}
// 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;
}