Leetcode 1088. Confusing Number II

Problem Explanation

This problem aims to find how many numbers between 1 and a given number, N, become 'confusing' when rotated 180 degrees. A number is 'confusing' if it becomes a different but valid number when rotated. Only digits [0,1,6,8,9] can be valid when rotated 180 degrees as they become [0,1,9,8,6] respectively, whereas [2,3,4,5,7] become invalid.

For example, given input number 20, the confusing numbers between 1 and 20 include [6,9,10,16,18,19].

Solution Approach

Our approach to this problem is Depth-First Search (DFS). DFS is a simple strategy where we start from a root (or choosing some arbitrary node as the root when the graph is not a tree), and explore as far as possible along each branch before backtracking.

We traverse each valid number until we reach N, then rotate each one and compare with the original number to determine whether it is a confusing number. This approach will visit all confusing numbers exactly once.

Python Solution

1
2python
3class Solution:
4 def findConfusingNumber(self, n: int, m: int, st: int) -> int:
5     if n < m:
6         return 0
7     res = m != st
8     # fives digits are valid when rotated: 0, 1, 6, 8, 9
9     for i in [0, 1, 6, 8, 9]:
10         if m == 0 and i == 0:
11             continue
12         if m * 10 + i > n:
13             break
14         # different process for each digit when rotated
15         if i == 0:
16             wen = st * 10
17         elif i == 1:
18             wen = st * 10 + 1
19         elif i == 6:
20             wen = st * 10 + 9
21         elif i == 8:
22             wen = st * 10 + 8
23         else:
24             wen = st * 10
25         res += self.findConfusingNumber(n, m*10 + i, wen)
26     return res
27
28 def confusingNumberII(self, N: int) -> int:
29     # four single-digit numbers are confusing number
30     return self.findConfusingNumber(N, 0, 0) - 4

Java Solution

1
2java
3class Solution {
4    int[] map = new int[]{0,1,-1,-1,-1,-1,9,-1,8,6};
5    int count = 0, N;
6
7    public int confusingNumberII(int N) {
8        this.N = N;
9        count = 0;
10        helper(0,0,0,1);
11        return count;
12    }
13
14    private void helper(int num, int rotation, int level, int base){
15        if(num!=rotation && num != 0) count++;
16        for(int i=0; i<10; i++){
17            if(num > N/base) return;
18            if(i == map[i] && num*10 == rotation) continue;
19            helper(num*10 + i, rotation*10 + map[i], level+1, base*10);
20        }
21    }
22}

JavaScript Solution

1
2javascript
3class Solution {
4  confusingNumberII(N) {
5    this.N = N;
6    this.map = [0,1,-1,-1,-1,-1,9,-1,8,6];
7    this.count = 0;
8    this.helper(0,0,0,1);
9    return this.count;
10  }
11
12  helper(num, rotation, level, base) {
13    if(num !== rotation && num !== 0) this.count++;
14    for(let i = 0; i < 10; i++){
15      if(num > this.N/base) return;
16      if(i === this.map[i] && num*10 === rotation) continue;
17      this.helper(num*10 + i, rotation*10 + this.map[i], level+1, base*10);
18    }
19  }
20}
21
22module.exports = Solution;

C++ Solution

1
2cpp
3const vector<pair<int,int>> digits={{0, 0}, {1, 1}, {6, 9}, {8, 8}, {9, 6}};
4    
5class Solution {
6public:
7    int confusingNumberII(int n) {
8        return dfs(n, 0, 0, 1);
9    }
10
11private:
12    int dfs(int n, long num, long rotated, int mask) {
13        int cnt = num != rotated;
14        for (auto [digit, rotate] : digits) {
15            if ((!num) && (!digit)) continue;
16            if ((num = num * 10 + digit) > n) break;
17            cnt += dfs(n, num, rotated + rotate * mask, mask * 10);
18            num /= 10;
19        }
20        return cnt;
21    }
22};

C# Solution

1
2csharp
3class Solution {
4    private Dictionary<int, int> confuseDigits = null;
5
6    public int ConfusingNumberII(int n){
7        confuseDigits = new Dictionary<int, int>
8        {
9            {0, 0}, {1, 1}, {6, 9}, {8, 8}, {9, 6}
10        };
11
12        var ans = 0;
13        for (var digit = 1; digit <= 9; digit++){//make sure not to start with zero
14            ans += Dfs(n, digit, confuseDigits[digit]);
15        }
16
17        return ans;
18    }
19
20    private int Dfs(int n, long num, long rotate){
21        if (num > n)
22            return 0;
23
24        var ans = num != rotate ? 1 : 0;
25
26        for (var d = 0; d <= 9; d++){
27            ans += Dfs(n, num*10 + d, confuseDigits[d] * (long)Math.Pow(10, num.ToString().Length) + rotate);
28        }
29
30        return ans;
31    }
32}

In all the solutions, we are using a depth-first search approach to explore all possible number combinations using the provided digits [0,1,6,8,9]. In each iteration, we rotate the numbers and check if they are valid and confusing. If the numbers are confusing and valid, we increment our count.There are a few key points to note in these solutions:

• The DFS approach involves generating all possible number combinations using the digits 0,1,6,8,9. This is done with a nested for loop which iteratively generates new numbers by multiplying the existing number by 10 and adding the next digit.

• To handle the rotation, the solutions map each digit to its corresponding rotated version; for example, 6 is mapped to 9 and vice versa, 8 is mapped to itself, and 0 and 1 are also mapped to themselves since their form does not change upon rotation. These mappings are used to generate the rotated version of each number.

• As numbers are generated and rotated, a check is performed to identify confusing numbers, i.e., numbers that are not the same as their rotated versions and do not exceed the given value N. This check simply involves comparing each generated number with its rotated version, and if the two numbers are not equal, incrementing a counter.

• These DFS algorithm is applied recursively until all possible number combinations within the limit of N have been exhausted.

• The confusingNumberII function in each solution acts as a wrapper for the DFS, initializing the necessary variables and calling the recursive function. The count of confusing numbers is then returned as the solution to the problem.

• One important thing to note is that in each solution, the DFS function starts with a number and its rotation, then for each digit to be appended, it recursively calls itself with both the new number and its rotation. This ensures all possible combinations are considered.

• It's also important to note that the Python solution deducts 4 at the end of the function confusingNumberII as there are four single-digit confusing numbers: 0, 1, 8, and the number itself under consideration if it's within the single-digit numbers. The function calculates these as confusing numbers, but according to the problem definition, they are not, and hence, are deducted at the end before returning the result.

Overall, these solutions effectively calculate the count of confusing numbers in a given range, showcasing the utility of depth-first search in problem-solving. As you can see, different programming languages offer slightly different methods to implement DFS, but the core logic stays the same.