Confusing Number II

Hard

Asked by:

29 views

Topics:

Recursion

We can rotate digits by 180 degrees to form new digits. When 0, 1, 6, 8, and 9 are rotated, they become 0, 1, 9, 8, and 6 respectively. When the rest of the digits are rotated, they do not become any numbers and are considered invalid.

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

For example, the number 021 is not a confusing number because it contains an invalid digit.
For example, the number 33 is not a confusing number because it contains an invalid digit.
For example, 19 is a confusing number because when rotated it becomes 61, which is different.
For example, 898 is a confusing number because when rotated it becomes 868, which is different.

Given an integer n, return the number of confusing numbers between 1 and n inclusive.

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,96,98,99].

Constraints:

1 <= n <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the upper bound for the input integer N? In other words, what is the maximum possible value of N?
Are we only considering positive integers? Should I handle the case where N is zero or negative?
Regarding the definition of a 'confusing number', is the input number itself allowed to be a confusing number that contributes to the total count?
If N is a small number such that no confusing numbers exist up to N, what should the return value be?
Are there any memory constraints I should be aware of, or is space complexity a secondary concern compared to accurately counting the confusing numbers?

Brute Force Solution

Approach

We're figuring out how many 'confusing numbers' exist up to a certain limit. The brute force approach involves checking every single number within that limit to see if it's a confusing number and counting the ones that are.

Here's how the algorithm would work step-by-step:

Start with the number 1 and go all the way up to the limit.
For each number, check if it's a valid digit combination that can be rotated (e.g., using only 0, 1, 6, 8, and 9).
If the number contains invalid digits, skip to the next number.
If the digits are valid, rotate the number by swapping digits (0 becomes 0, 1 becomes 1, 6 becomes 9, 8 becomes 8, and 9 becomes 6).
Reverse the order of the rotated digits.
Compare the original number with the rotated number to see if they are different.
If the numbers are different, it's a confusing number, so count it.
Continue this process for every number up to the limit.
The final count is the total number of confusing numbers.

Code Implementation

def confusing_number_two_brute_force(limit):
    confusing_number_count = 0

    for number in range(1, limit + 1):
        number_string = str(number)
        is_valid = True

        for digit_char in number_string:
            digit = int(digit_char)
            if digit not in [0, 1, 6, 8, 9]:
                is_valid = False
                break

        if not is_valid:
            continue

        rotated_digits = []

        # Rotate each digit of the current number
        for digit_char in number_string:
            digit = int(digit_char)
            if digit == 0:
                rotated_digits.append('0')
            elif digit == 1:
                rotated_digits.append('1')
            elif digit == 6:
                rotated_digits.append('9')
            elif digit == 8:
                rotated_digits.append('8')
            elif digit == 9:
                rotated_digits.append('6')

        rotated_number_string = ''.join(rotated_digits[::-1])

        # Crucial: comparing the original and rotated values
        if number_string != rotated_number_string:
            confusing_number_count += 1

    return confusing_number_count

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm iterates through all numbers from 1 to n. For each number, it performs digit validation and rotation. The number of digits in a number k is approximately log10(k), which is O(log k). Therefore, the digit validation and rotation take O(log n) time in the worst case since we iterate to n. Overall, the time complexity becomes O(n log n).

Space Complexity

O(log N) – The space complexity is primarily determined by the depth of the recursion stack during the digit rotation and validation process. The maximum depth of the recursion is proportional to the number of digits in the input number N. Therefore, the recursion stack can grow up to log base 10 of N. The other variables used in the process take up constant space regardless of the input size. The space used by the recursion stack dominates the auxiliary space.

Optimal Solution

Approach

The problem asks us to count special numbers within a given limit. Instead of checking every single number to see if it's confusing, we generate confusing numbers in increasing order and count how many are within the limit. This significantly reduces computation time by avoiding unnecessary checks.

Here's how the algorithm would work step-by-step:

Identify the digits that can be rotated to form another digit: 0, 1, 6, 8, and 9. These are the only digits we need to consider.
Start generating potential confusing numbers using only these allowed digits.
For each potential number, check if it's a valid confusing number (i.e., its rotated version is different).
If the number is valid and less than or equal to the input limit, increment the count.
Continue generating larger numbers, but stop exploring a branch if the current number exceeds the limit, as all numbers generated from that point will also be too large.
Repeat this process until all possible confusing numbers within the limit have been explored. The count is the answer.

Code Implementation

def confusingNumberII(maximum_limit):
    allowed_digits = [0, 1, 6, 8, 9]
    rotation_map = {0: 0, 1: 1, 6: 9, 8: 8, 9: 6}
    count = 0

    def is_confusing(number):
        rotated_number = 0
        temp_number = number
        power_of_ten = 1

        while temp_number > 0:
            digit = temp_number % 10
            rotated_digit = rotation_map[digit]
            rotated_number = rotated_number * 10 + rotated_digit
            temp_number //= 10
            power_of_ten *= 10

        return rotated_number != number

    def generate_confusing_numbers(current_number):
        nonlocal count

        # Stop recursion if current number is too big
        if current_number > maximum_limit:
            return

        # Check if the number is valid and increment counter
        if current_number != 0 and is_confusing(current_number):
            count += 1

        # Generate all possible next numbers
        for digit in allowed_digits:
            next_number = current_number * 10 + digit
            generate_confusing_numbers(next_number)

    # Start generating numbers from each allowed digit.
    for digit in allowed_digits:
        generate_confusing_numbers(digit)

    return count

Big(O) Analysis

Time Complexity

O(log_5(n)) – The input size is represented by the limit n. The algorithm generates confusing numbers using the digits 0, 1, 6, 8, and 9. The number of possible confusing numbers to generate grows logarithmically with respect to the limit n, with a base of 5 (since we are using 5 digits to generate these numbers). Therefore, the time complexity is roughly proportional to the number of generated confusing numbers before exceeding n. Consequently, the algorithm's runtime is O(log_5(n)).

Space Complexity

O(log N) – The space complexity is primarily determined by the depth of the recursion used to generate confusing numbers. Since we generate numbers in increasing order, the number of digits in the generated numbers grows logarithmically with the input limit N. The maximum recursion depth will be proportional to the number of digits, hence log N. The auxiliary space needed is dominated by the call stack of the recursive calls used to explore the space of valid confusing numbers. Therefore, the space complexity is O(log N).

Edge Cases

Case	How to Handle
Input n is 0	Return 0 because 0 is not a confusing number as it reads the same rotated.
Input n is a single digit confusing number (2, 5, 6, 9)	Return 1 as only one such number exists.
Input n contains only digits that rotate to themselves (0, 1, 8)	Return 0 since no confusing numbers exist.
Integer overflow during number generation (exceeding max int)	Use long data type to avoid overflow and check for long > Integer.MAX_VALUE during generation.
Input n is a large number (e.g., close to Integer.MAX_VALUE)	Optimize number generation to avoid exploring branches exceeding n.
Input n contains non-rotatable digits like 3, 4, 7	The generation logic should only create numbers with valid rotatable digits (0, 1, 6, 8, 9, 2, 5).
Numbers starting with 0 after rotation	Prevent generating numbers whose rotations will start with a zero.
Generating the same number via different rotation combinations.	Use a Set to deduplicate confusing numbers that are generated.

Input n is 0

How to Handle:

Return 0 because 0 is not a confusing number as it reads the same rotated.

Input n is a single digit confusing number (2, 5, 6, 9)

How to Handle:

Return 1 as only one such number exists.

Input n contains only digits that rotate to themselves (0, 1, 8)

How to Handle:

Return 0 since no confusing numbers exist.

Integer overflow during number generation (exceeding max int)

How to Handle:

Use long data type to avoid overflow and check for long > Integer.MAX_VALUE during generation.

Input n is a large number (e.g., close to Integer.MAX_VALUE)

How to Handle:

Optimize number generation to avoid exploring branches exceeding n.

Input n contains non-rotatable digits like 3, 4, 7

How to Handle:

The generation logic should only create numbers with valid rotatable digits (0, 1, 6, 8, 9, 2, 5).

Numbers starting with 0 after rotation

How to Handle:

Prevent generating numbers whose rotations will start with a zero.

Generating the same number via different rotation combinations.

How to Handle:

Use a Set to deduplicate confusing numbers that are generated.