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

All Problems

All Solutions