LeetCode [1088] Confusing Number II

1088. Confusing Number II

Hard

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

//Java
class Solution {
    int[] map = new int[10];
    int ret = 0;
    public int confusingNumberII(int N) {
        map[0] = 0;
        map[1] = 1;
        map[6] = 9;
        map[8] = 8;
        map[9] = 6;
        helper(0, N);
        return ret;
    }

    void helper(long cur, int N){
        if(valid(cur)) ret++;
        for(int i : new int[]{0,1,6,8,9}){
            long next = cur * 10 + i;
            if(next<=(long)N && next!=0) helper(next, N);
        }
    }

    boolean valid(long v){
        long src = v;
        long ret = 0;
        while(src>0){
            ret = ret*10+map[(int)src%10];
            src = src/10;
        }
        return ret!=v;
    }
}