Confusing Number Ii - Leetcode Solution

Problem Statement:

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.

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 not a different number. 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,96,98,99].

Approach:

We know that the confusing numbers are those numbers which are not equal to their 180-degree rotation. So, we have to generate all the numbers which are not palindromes and for which every digit in the resulting 180-degree rotation is valid.

To generate these numbers, we traverse all the valid digits (0,1,6,8,9) and generate all possible numbers of a specific length. Then we rotate them by 180 degrees and check whether the resulting number is different from the original number, and if it is a valid number. If yes, we add it to our answer.

Implementation:

Let's discuss the implementation in detail.

First, we define a function isConfusingNumber(num) which takes a number as input and returns true if it is a confusing number.

We rotate each digit in num by 180 degrees, and if any digit is invalid or if the resulting number is equal to the original number, it is not a confusing number and we return False.

Next, we define a function generateConfusingNumbers(num, length) that takes two arguments, num and length. This function recursively generates all possible numbers of length length using the digits 0,1,6,8, and 9, and starting with the given num. We do this by first checking if the length is 0, in which case we check if the number is a confusing number and return 1 if it is, and 0 otherwise. If the length is greater than 0, we append each valid digit to the end of num, and recursively call the same function with the num and length decremented by 1. We add the number of confusing numbers generated by each call to the total and return it.

Finally, in the main function, we generate all confusing numbers of length 1, 2, ..., len(str(n))-1 (if n has more than one digit), then we generate confusing numbers of length len(str(n)) up to n, and return the total.

Time Complexity:

The time complexity of the solution is O(5^m * m), where m is the length of the largest number n. This is because we generate all possible numbers of length 1, 2, ..., m, and for each number generated, we check if it is a confusing number (which takes O(m) time).

Space Complexity:

The space complexity of the solution is O(m), where m is the length of the largest number n. This is because we store the current number being generated during the recursive function calls.

1