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

All Problems

All Solutions