Welcome to Subscribe On Youtube

1088. Confusing Number II

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:

  • 1 <= n <= 109

Solutions

  • 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; } } 
  • 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); }

All Problems

All Solutions