1088. Confusing Number II

A confusing number is a number that when rotated 180 degrees becomes a different number with each digit valid.

We can rotate digits of a number by 180 degrees to form new digits.

• When 0, 1, 6, 8, and 9 are rotated 180 degrees, they become 0, 1, 9, 8, and 6 respectively.

• When 2, 3, 4, 5, and 7 are rotated 180 degrees, they become invalid.

Note that after rotating a number, we can ignore leading zeros.

• For example, after rotating 8000, we have 0008 which is considered as just 8.

Given an integer n, return the number of confusing numbers in the inclusive range [1, n].

Example 1:

Input: n = 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: n = 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].

Constraints:

• 1 <= n <= 10^9

Solution

The initial idea is to iterate all numbers in the range and check if it is a confusing number.

To reduce the impossible case, we trying to build up the possible combination by [0, 1, 6, 8, 9].

Because we want to know what is the rotated result of these digits, we decide to use a Map to keep the informs

Map <K, V> : K: the src digit , ex : 6 V: the rotated digit ex: 9

And we using DFS to trace all possible results by iteration of map.keySet(), and additionally check if the rotated result should not be equal to the source.

Map<Integer, Integer> map = new HashMap<>();
int count = 0;

public int confusingNumberII(int n){
    map.put(0, 0);
    map.put(1, 1);
    map.put(6, 9);
    map.put(8, 8);
    map.put(9, 6);
    dfs(0, n);
    return count;
}

public void dfs(long curNum, int n){
    if(isConfusing(curNum)){
        count++;
    }
    for(int num : map.keySet()){
        long newNum = curNum*10 + num;
        if(newNum <= n && newNum != 0){
            dfs(newNum, n);
        }
    }
}

public boolean isConfusing(long num){
    long src = num;
    long revert = 0;
    while(num > 0) {
        revert = revert * 10 + map.get((int) num%10);
        num = num / 10;
    }
    return revert != src;
}