Jobs

Interviews

Discussions

Confusing Number

Easy

Google

6 views

Topics:

Strings

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

We can rotate digits as follows:

0, 1, 8 rotate to themselves,
2 and 5 rotate to each other (in this case they are different),
6 and 9 rotate to each other (in this case they are different),
The rest of the digits do not rotate to any other digit and are invalid.

Given an integer n, return true if it is a confusing number, or false otherwise.

Example 1:

Input: n = 6
Output: true
Explanation: We get 9 after rotating 6, 9 is different than 6.

Example 2:

Input: n = 89
Output: true
Explanation: We get 68 after rotating 89, 68 is different than 89.

Example 3:

Input: n = 11
Output: false
Explanation: We get 11 after rotating 11, 11 is the same as 11.

Constraints:

0 <= n <= 10⁹

Try coding it in LeetCode

Confusing Number

Easy

Google

6 views

Topics:

Strings

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

We can rotate digits as follows:

0, 1, 8 rotate to themselves,
2 and 5 rotate to each other (in this case they are different),
6 and 9 rotate to each other (in this case they are different),
The rest of the digits do not rotate to any other digit and are invalid.

Given an integer n, return true if it is a confusing number, or false otherwise.

Example 1:

Input: n = 6
Output: true
Explanation: We get 9 after rotating 6, 9 is different than 6.

Example 2:

Input: n = 89
Output: true
Explanation: We get 68 after rotating 89, 68 is different than 89.

Example 3:

Input: n = 11
Output: false
Explanation: We get 11 after rotating 11, 11 is the same as 11.

Constraints:

0 <= 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 range of the input integer? Can it be negative?
Are we considering only positive integers or should I account for zero as well?
If the input integer is not a confusing number, what should the function return? Should I return null, false or throw an exception?
Can you please clarify the definition of "confusing number" with an example? How are the rotated digits handled?
Should I consider the reversed number to be different from the original number?

Brute Force Solution

Approach

To solve this 'Confusing Number' problem the hard way, we'll check every single number from 1 up to the given number. For each number, we'll see if it's a 'confusing number' based on the rules.

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

Start with the number 1.
Check if 1 is a 'confusing number'. This means we need to rotate it, and see if the rotated number is different from the original.
Move on to the next number, 2.
Check if 2 is a 'confusing number' by rotating it and comparing to the original.
Keep doing this, checking each number one by one.
When you find a number that is 'confusing', make note of it.
Continue until you reach the number given to you.
Finally, count how many 'confusing numbers' you found along the way.

Code Implementation

def confusing_number_brute_force(number_limit):
    confusing_numbers_count = 0

    for current_number in range(1, number_limit + 1):
        rotated_number = rotate_number(current_number)

        # Check if the rotated number is different from the original
        if rotated_number != current_number:
            confusing_numbers_count += 1

    return confusing_numbers_count

def rotate_number(number):
    number_string = str(number)
    rotated_string = ''

    valid_rotations = {'0': '0', '1': '1', '6': '9', '8': '8', '9': '6'}

    for digit in reversed(number_string):
        # Invalid numbers like 2, 3, 4, 5, 7 are not confusing.
        if digit not in valid_rotations:
            return -1

        rotated_string += valid_rotations[digit]

    return int(rotated_string)

Big(O) Analysis

Time Complexity

O(n log n) – The described approach iterates through all numbers from 1 to n. For each number i, the algorithm performs a 'rotation' operation, which involves converting the number to a string, iterating through its digits, and potentially performing a lookup to find the rotated digit. Assuming the number of digits is proportional to log(i) (and therefore at most log(n)), rotating the number takes O(log n) time. Since we iterate through 'n' numbers, and each rotation takes O(log n) time, the total time complexity is O(n log n).

Space Complexity

O(1) – The provided approach iterates from 1 to N, checking each number. The only extra memory used is for a few constant-size variables within the loop to store temporary results during the rotation and comparison process. Regardless of the value of N, the amount of auxiliary memory remains constant. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The task is to determine if a number is confusing. A confusing number is one that, when rotated 180 degrees, becomes a different valid number. Instead of checking every number up to the input, we'll focus on figuring out which numbers can be rotated to create a new valid number.

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

First, define which digits can be rotated and what they become. For example, 0 rotates to 0, 1 rotates to 1, 6 rotates to 9, 8 rotates to 8, and 9 rotates to 6. Other digits are invalid.
Create a function to rotate a given number. This function will transform the original number into its rotated counterpart based on the valid digit rotations.
Now, rotate the input number using this function.
Compare the rotated number with the original number. If the rotated number is different from the original number, then the number is confusing.
If the rotated number is the same as the original or if the rotation process resulted in an invalid number (containing digits that cannot be rotated), then it's not a confusing number.

Code Implementation

def is_confusing_number(number):
    rotation_map = {
        '0': '0',
        '1': '1',
        '6': '9',
        '8': '8',
        '9': '6'
    }

    number_string = str(number)
    rotated_string = ''

    # Iterating in reverse to simulate 180-degree rotation
    for digit in reversed(number_string):
        if digit not in rotation_map:
            return False

        rotated_string += rotation_map[digit]

    rotated_number = int(rotated_string)

    # Numbers must be different after rotation to be considered 'confusing'
    if rotated_number != number:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

O(log n) – The primary operation involves rotating the input number n, which requires iterating through its digits. The number of digits in n is proportional to log n (base 10). Therefore, the rotation process takes O(log n) time. Comparing the rotated number to the original takes constant time, O(1). Hence, the overall time complexity is dominated by the rotation, resulting in O(log n).

Space Complexity

O(log N) – The space complexity is determined by the function used to rotate the given number. Specifically, converting the number to a string or list of digits requires space proportional to the number of digits in N, which is logarithmic in relation to N (the number of digits in N is log base 10 of N). Furthermore, the function to rotate the number may create a new string or list to store the rotated digits, contributing an additional O(log N). No other significant data structures are used, so the auxiliary space is O(log N).

Edge Cases

Case	How to Handle
Input N is zero	Return False as 0 is not a confusing number as it becomes 0 when rotated.
Input N is a negative number	Return False since the problem deals with positive integers and rotation does not apply to negative integers.
Input N contains digits other than 0, 1, 6, 8, and 9	Return False immediately since any other digits are invalid.
Input N is a single digit number (e.g., 0, 1, 6, 8, 9)	Return True only if the rotated number is different; 0, 1, and 8 will return False and 6/9 will return True.
Input N is a large number that may cause integer overflow during rotation	Use appropriate data types (e.g., long) to prevent potential integer overflows during the rotation process.
Input N has leading zeros, potentially altering the confusing number result.	Treat the number as an integer, which implicitly ignores the leading zeros, before processing.
All digits of N are the same, resulting in the same number after rotation.	If all digits are 0, 1, or 8, then it is not a confusing number, and should return false.
Input N is the maximum integer value.	Handle the rotation of each digit carefully to prevent overflow or incorrect mapping.

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 range of the input integer? Can it be negative?
Are we considering only positive integers or should I account for zero as well?
If the input integer is not a confusing number, what should the function return? Should I return null, false or throw an exception?
Can you please clarify the definition of "confusing number" with an example? How are the rotated digits handled?
Should I consider the reversed number to be different from the original number?

Brute Force Solution

Approach

To solve this 'Confusing Number' problem the hard way, we'll check every single number from 1 up to the given number. For each number, we'll see if it's a 'confusing number' based on the rules.

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

Start with the number 1.
Check if 1 is a 'confusing number'. This means we need to rotate it, and see if the rotated number is different from the original.
Move on to the next number, 2.
Check if 2 is a 'confusing number' by rotating it and comparing to the original.
Keep doing this, checking each number one by one.
When you find a number that is 'confusing', make note of it.
Continue until you reach the number given to you.
Finally, count how many 'confusing numbers' you found along the way.

Code Implementation

def confusing_number_brute_force(number_limit):
    confusing_numbers_count = 0

    for current_number in range(1, number_limit + 1):
        rotated_number = rotate_number(current_number)

        # Check if the rotated number is different from the original
        if rotated_number != current_number:
            confusing_numbers_count += 1

    return confusing_numbers_count

def rotate_number(number):
    number_string = str(number)
    rotated_string = ''

    valid_rotations = {'0': '0', '1': '1', '6': '9', '8': '8', '9': '6'}

    for digit in reversed(number_string):
        # Invalid numbers like 2, 3, 4, 5, 7 are not confusing.
        if digit not in valid_rotations:
            return -1

        rotated_string += valid_rotations[digit]

    return int(rotated_string)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, define which digits can be rotated and what they become. For example, 0 rotates to 0, 1 rotates to 1, 6 rotates to 9, 8 rotates to 8, and 9 rotates to 6. Other digits are invalid.
Create a function to rotate a given number. This function will transform the original number into its rotated counterpart based on the valid digit rotations.
Now, rotate the input number using this function.
Compare the rotated number with the original number. If the rotated number is different from the original number, then the number is confusing.
If the rotated number is the same as the original or if the rotation process resulted in an invalid number (containing digits that cannot be rotated), then it's not a confusing number.

Code Implementation

def is_confusing_number(number):
    rotation_map = {
        '0': '0',
        '1': '1',
        '6': '9',
        '8': '8',
        '9': '6'
    }

    number_string = str(number)
    rotated_string = ''

    # Iterating in reverse to simulate 180-degree rotation
    for digit in reversed(number_string):
        if digit not in rotation_map:
            return False

        rotated_string += rotation_map[digit]

    rotated_number = int(rotated_string)

    # Numbers must be different after rotation to be considered 'confusing'
    if rotated_number != number:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input N is zero	Return False as 0 is not a confusing number as it becomes 0 when rotated.
Input N is a negative number	Return False since the problem deals with positive integers and rotation does not apply to negative integers.
Input N contains digits other than 0, 1, 6, 8, and 9	Return False immediately since any other digits are invalid.
Input N is a single digit number (e.g., 0, 1, 6, 8, 9)	Return True only if the rotated number is different; 0, 1, and 8 will return False and 6/9 will return True.
Input N is a large number that may cause integer overflow during rotation	Use appropriate data types (e.g., long) to prevent potential integer overflows during the rotation process.
Input N has leading zeros, potentially altering the confusing number result.	Treat the number as an integer, which implicitly ignores the leading zeros, before processing.
All digits of N are the same, resulting in the same number after rotation.	If all digits are 0, 1, or 8, then it is not a confusing number, and should return false.
Input N is the maximum integer value.	Handle the rotation of each digit carefully to prevent overflow or incorrect mapping.