1088.txt

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









class Solution {
public:
    int N;
    int res=0;

    int confusingNumberII(int N) {
        this->N=N;
        unordered_map<int, int> hash{{0, 0}, {1, 1}, {6, 9}, {8, 8}, {9, 6}};
        vector<int>A={0,1,6,8,9};
        for(int i=1;i<A.size();i++){
            dfs(hash,A,A[i]);
        }
        return res;
    }
    
    void dfs(unordered_map<int, int> &hash,vector<int>&A,long long cur){
        if(cur>N)return;
        
        if(isValid(hash,cur)){
            res++;
        }
        
        for(int i:A){
            dfs(hash,A,cur*10+i);
        }
    }
    
     bool isValid(unordered_map<int,int>&hash,long long n) {
        long long src = n;
        long long res = 0;
        while (n > 0) {
            res = res * 10 + hash[n%10]; 
            n /= 10;
        }
        return src!=res;
    }
    
};