LeetCode/1088. Confusing Number II (Backtracking) 20.6.4 Hard at master · BrianSong/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
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


Solution: O(5^k) T and O(k) S where k is the digits number of N
class Solution(object):
    def confusingNumberII(self, N):
        """
        :type N: int
        :rtype: int
        """
        valid_digit = [0, 1, 6, 8, 9]
        match = {0 : 0, 1 : 1, 6 : 9, 8 : 8, 9 : 6}
        self.count = 0

        def backtracking(curr, rotation, time):
            if curr != rotation:
                self.count += 1
            for digit in valid_digit:
                if curr * 10 + digit >  N:
                    break
                backtracking(curr * 10 + digit, match[digit] * time + rotation, time * 10)

        backtracking(1, 1, 10)
        backtracking(6, 9, 10)
        backtracking(8, 8, 10)
        backtracking(9, 6, 10)

        return self.count