# 1088. Confusing Number II
###### tags: `Leetcode` `Hard` `Backtracking` `Math`
Link: https://leetcode.com/problems/confusing-number-ii/
## 思路
直觉的想法是用backtracking
但其实是有点没效率的 因为例如n的长度=5 那么我们可以用数学方法算出来长度小于等于4的confusing number一共有多少个
然后再用backtracking算长度等于5且小于n的confusing number

数学方法为:
首先，我们知道confusing number只能用0,1,6,8,9这五个数字组数。先考虑给定这个digit集合能组成多少个长度为len的数？显然答案是```4*pow(5,len-1)```，其中4是考虑到了高位首位不能为零。

然后我们考虑在上述这些数中间有多少non-confusing number呢？Non-confusing number的定义就是翻转之后和原来的数字一样，也就是说，相对中间位置对称的两个digit需要是翻转对称的（也就是1->1,6->9,8->8,9->6,0->0），并且如果长度是奇数那么中间一个digit与自己翻转堆成（也就是1->1,8->8,0->0）.所以对于长度为len的数，non-confusing number的个数的计算方法：

if (len%2==0)        
    return 4*pow(5,len/2-1);
else
    return 4*pow(5,len/2-1)*3;

同理，4表示高位第一位不能是0，所以是四种选择。3表示长度是奇数时，中间一个digit的选择只有三种。其他位置（从高位第一位到中间一位）的选择是五种。```len/2```的操作是因为，对于non-confusing number，只要确定了前一般长度的digit，后一半的digit也就确定了。

所以对于长度等于len的confusing number，就是上面计算得到的两个结果之差。

**注意**: 当len=1时特别考虑因为```4*pow(5, len/2-1)*3```在len=1时会变成0 len=1时有两个confusing number

然后我们再用backtracking算出小于n并且长度等于n的长度的confusing number的个数
## Code

class Solution {
    int ans;
    public int confusingNumberII(int n) {
        int len = String.valueOf(n).length();
        ans = 2;
        for(int i=2; i<len; i++){
            ans += confusingNumberGivenLen(i);
        }
        int[] num = new int[]{0,1,6,8,9};
        backtracking(num, 0, 0L, len, n);
        return ans;
    }
    public void backtracking(int[] num, int currLen, long currNum, int len, int n){
        if(currLen==len){
            if(currNum<=n && isConfusingNumber(currNum)){
                ans++;
            }
            return;
        }
        currNum *= 10;
        for(int i=0; i<num.length; i++){
            if(currLen==0 && i==0) continue;
            backtracking(num, currLen+1, currNum+num[i], len, n);
        }
    }
    public int confusingNumberGivenLen(int len){
        long ans = 4*(int)Math.pow(5, len-1);
        if(len%2==0) ans -= 4*(int)Math.pow(5, len/2-1);
        else ans -= 4*(int)Math.pow(5, len/2-1)*3;
        return (int)ans;
    }
    public boolean isConfusingNumber(long n){
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0,0);
        map.put(1,1);
        map.put(8,8);
        map.put(6,9);
        map.put(9,6);
        char[] arr = String.valueOf(n).toCharArray();
        int left=0, right = arr.length-1;
        while(left<=right){
            if(map.get(arr[left]-'0')!=arr[right]-'0') return true;
            left++;
            right--;
        }
        return false;
    }
}