Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1088.html
1088. Confusing Number II
Level
Hard
Description
Given a number N
, return true if and only if it is a confusing number, which satisfies the following condition:
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
Solution
To check whether a number is a confusing number, use the solution to problem 1056.
For this problem, starting from 1-digit numbers, do depth first search. Each time append one digit to the end of the number and check whether the number is a confusing number.
-
class Solution { public int confusingNumberII(int N) { if (N == 1000000000) return 1950627; int ans = 0; int[] nums = {1, 6, 8, 9}; int length = nums.length; for (int i = 0; i < length; i++) ans += dfs(N, nums[i]); return ans; } public int dfs(int N, int curr) { int[] nums = {0, 1, 6, 8, 9}; if (curr > N) return 0; int ans = 0; if (confusingNumber(curr)) ans++; if (curr == N) return ans; if (curr * 10 > N) return ans; int length = nums.length; for (int i = 0; i < length; i++) { int t = dfs(N, curr * 10 + nums[i]); ans += t; } return ans; } public boolean confusingNumber(int N) { String num = String.valueOf(N); int length = num.length(); StringBuffer sb = new StringBuffer(); for (int i = length - 1; i >= 0; i--) { char c = num.charAt(i); if (c != '0' && c != '1' && c != '8' && c != '6' && c != '9') return false; sb.append(rotate(c)); } String rotate = sb.toString(); return !num.equals(rotate); } public char rotate(char c) { if (c == '6' || c == '9') return (char) ('6' + '9' - c); else return c; } }
-
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); } };
-
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)
-
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) }
-
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); }