Description#
A confusing number is a number that when rotated 180 degrees becomes a different number with each digit valid.
We can rotate digits of a number by 180 degrees to form new digits.
- When
0, 1, 6, 8, and 9 are rotated 180 degrees, they become 0, 1, 9, 8, and 6 respectively. - When
2, 3, 4, 5, and 7 are rotated 180 degrees, they become invalid.
Note that after rotating a number, we can ignore leading zeros.
- For example, after rotating
8000, we have 0008 which is considered as just 8.
Given an integer n, return the number of confusing numbers in the inclusive range [1, n].
Example 1:
Input: n = 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: n = 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].
Constraints:
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution:
def confusingNumberII(self, n: int) -> int:
def check(x: int) -> bool:
y, t = 0, x
while t:
t, v = divmod(t, 10)
y = y * 10 + d[v]
return x != y
def dfs(pos: int, limit: bool, x: int) -> int:
if pos >= len(s):
return int(check(x))
up = int(s[pos]) if limit else 9
ans = 0
for i in range(up + 1):
if d[i] != -1:
ans += dfs(pos + 1, limit and i == up, x * 10 + i)
return ans
d = [0, 1, -1, -1, -1, -1, 9, -1, 8, 6]
s = str(n)
return dfs(0, True, 0)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
private final int[] d = {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
private String s;
public int confusingNumberII(int n) {
s = String.valueOf(n);
return dfs(0, 1, 0);
}
private int dfs(int pos, int limit, int x) {
if (pos >= s.length()) {
return check(x) ? 1 : 0;
}
int up = limit == 1 ? s.charAt(pos) - '0' : 9;
int ans = 0;
for (int i = 0; i <= up; ++i) {
if (d[i] != -1) {
ans += dfs(pos + 1, limit == 1 && i == up ? 1 : 0, x * 10 + i);
}
}
return ans;
}
private boolean check(int x) {
int y = 0;
for (int t = x; t > 0; t /= 10) {
int v = t % 10;
y = y * 10 + d[v];
}
return x != y;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public:
int confusingNumberII(int n) {
string s = to_string(n);
int d[10] = {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
auto check = [&](int x) -> bool {
int y = 0;
for (int t = x; t; t /= 10) {
int v = t % 10;
y = y * 10 + d[v];
}
return x != y;
};
function<int(int, int, int)> dfs = [&](int pos, int limit, int x) -> int {
if (pos >= s.size()) {
return check(x);
}
int up = limit ? s[pos] - '0' : 9;
int ans = 0;
for (int i = 0; i <= up; ++i) {
if (d[i] != -1) {
ans += dfs(pos + 1, limit && i == up, x * 10 + i);
}
}
return ans;
};
return dfs(0, 1, 0);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| func confusingNumberII(n int) int {
d := [10]int{0, 1, -1, -1, -1, -1, 9, -1, 8, 6}
s := strconv.Itoa(n)
check := func(x int) bool {
y := 0
for t := x; t > 0; t /= 10 {
v := t % 10
y = y*10 + d[v]
}
return x != y
}
var dfs func(pos int, limit bool, x int) int
dfs = func(pos int, limit bool, x int) (ans int) {
if pos >= len(s) {
if check(x) {
return 1
}
return 0
}
up := 9
if limit {
up = int(s[pos] - '0')
}
for i := 0; i <= up; i++ {
if d[i] != -1 {
ans += dfs(pos+1, limit && i == up, x*10+i)
}
}
return
}
return dfs(0, true, 0)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| function confusingNumberII(n: number): number {
const s = n.toString();
const d: number[] = [0, 1, -1, -1, -1, -1, 9, -1, 8, 6];
const check = (x: number) => {
let y = 0;
for (let t = x; t > 0; t = Math.floor(t / 10)) {
const v = t % 10;
y = y * 10 + d[v];
}
return x !== y;
};
const dfs = (pos: number, limit: boolean, x: number): number => {
if (pos >= s.length) {
return check(x) ? 1 : 0;
}
const up = limit ? parseInt(s[pos]) : 9;
let ans = 0;
for (let i = 0; i <= up; ++i) {
if (d[i] !== -1) {
ans += dfs(pos + 1, limit && i === up, x * 10 + i);
}
}
return ans;
};
return dfs(0, true, 0);
}
|
