Jobs

Interviews

Discussions

Strobogrammatic Number II

Medium

Asked by:

48 views

Topics:

Recursion

Given an integer n, return all the strobogrammatic numbers of length n.

You can return the answer in any order.

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Example 1:

Input: n = 2
Output: ["11","69","88","96"]

Example 2:

Input: n = 1
Output: ["0","1","8"]

Constraints:

1 <= n <= 15

Try coding it in LeetCode

Strobogrammatic Number II

Medium

Asked by:

48 views

Topics:

Recursion

Given an integer n, return all the strobogrammatic numbers of length n.

You can return the answer in any order.

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Example 1:

Input: n = 2
Output: ["11","69","88","96"]

Example 2:

Input: n = 1
Output: ["0","1","8"]

Constraints:

1 <= n <= 15

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:

Given the integer 'n', representing the length of the strobogrammatic numbers, what is the maximum value of 'n'?
Should the generated strobogrammatic numbers be represented as strings or integers?
Are leading zeros allowed in the strobogrammatic numbers generated (except for the single digit '0' when n=1)?
If n is 0, should I return an empty list, or is that an invalid input?
Is there a specific ordering required for the generated strobogrammatic numbers (e.g., lexicographical)? If multiple valid solutions exist, do you require a specific order?

Brute Force Solution

Approach

We are looking for special numbers that look the same when turned upside down. The brute force method tries every possible combination of digits to find these numbers by building them one by one.

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

Start by considering all possible single-digit numbers.
Check if each of these single-digit numbers is strobogrammatic (looks the same upside down).
If we need to create longer numbers, consider all possible two-digit numbers, then three-digit numbers, and so on.
For each number we create, check if it is strobogrammatic.
If the number is strobogrammatic, keep it. If not, discard it.
Repeat this process until we have considered all numbers of the required length.
Finally, list all the strobogrammatic numbers that we found.

Code Implementation

def find_all_strobogrammatic_numbers_brute_force(number_length):
    strobogrammatic_pairs = [('0', '0'), ('1', '1'), ('6', '9'), ('8', '8'), ('9', '6')]

    def is_strobogrammatic(number_string):
        left_index = 0
        right_index = len(number_string) - 1
        while left_index <= right_index:
            if (number_string[left_index], number_string[right_index]) in strobogrammatic_pairs:
                left_index += 1
                right_index -= 1
            else:
                return False
        return True

    def generate_numbers(current_length, max_length):
        if current_length > max_length:
            return []

        if current_length == max_length:
            if current_length == 1:
                return ['0', '1', '8']
            return []

        if current_length == 1:
            result = ['0', '1', '8']
        else:
            result = [str(digit) for digit in range(10)]

        strobogrammatic_numbers = []
        for number in result:
            if len(number) == max_length and number[0] == '0':
                continue

            if is_strobogrammatic(number):
                strobogrammatic_numbers.append(number)

        for length in range(2, max_length + 1):
            new_numbers = []
            for first_digit in range(10):
                for last_digit in range(10):
                    new_number = str(first_digit) + str(last_digit)
                    if len(new_number) == length and new_number[0] == '0':
                        continue

                    if is_strobogrammatic(new_number):
                        strobogrammatic_numbers.append(new_number)

            for current_number in generate_numbers(length, max_length):
                if is_strobogrammatic(current_number):
                    strobogrammatic_numbers.append(current_number)

        return strobogrammatic_numbers

    all_possible_numbers = []
    for length_of_number in range(1, number_length + 1):
        all_numbers_of_length = [''.join(combination) for combination in product('0123456789', repeat=length_of_number)]

        for number_string in all_numbers_of_length:
            # Exclude numbers starting with zero if length > 1
            if len(number_string) > 1 and number_string[0] == '0':
                continue

            # Check if the number is strobogrammatic and append if it is
            if is_strobogrammatic(number_string):
                all_possible_numbers.append(number_string)

    from itertools import product

    strobogrammatic_numbers_final = []
    for length in range(1, number_length + 1):
        # Iterate through all possible digit combinations.
        all_combinations = [''.join(combination) for combination in product('0123456789', repeat=length)]

        for number_string in all_combinations:
            if len(number_string) > 1 and number_string[0] == '0':
                continue

            #Filter out any numbers that are not strobogrammatic
            if is_strobogrammatic(number_string):
                strobogrammatic_numbers_final.append(number_string)

    result = []
    for number_string in strobogrammatic_numbers_final:

        if len(number_string) == number_length:
             #Only return the numbers that match the target number_length
            result.append(number_string)

    return result

Big(O) Analysis

Time Complexity

O(5^(n/2)) – The brute force approach generates all possible digit combinations of length n. At each position in the number (excluding the first and last, which have fewer options), we have 5 possible digits that can form a strobogrammatic pair (0, 1, 6, 8, 9). Since we build the number from the middle outwards, we effectively consider approximately n/2 positions. Therefore, the number of combinations grows exponentially with a base related to the number of possible digit choices, leading to a time complexity of roughly O(5^(n/2)).

Space Complexity

O(5^N) – The brute force approach explores all possible digit combinations of length N, where N is the desired length of the strobogrammatic number. In the worst case, the recursion tree expands to consider combinations involving digits 0, 1, 6, 8, and 9. The number of strobogrammatic numbers generated grows exponentially, potentially storing up to 5^(N/2) numbers. Therefore, the auxiliary space needed to store these candidate numbers is O(5^(N/2)), which simplifies to O(5^N).

Optimal Solution

Approach

The best way to find all strobogrammatic numbers of a given length is to build them systematically. We start with the shortest valid strobogrammatic numbers and then extend them outwards until we reach the desired length.

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

Recognize that strobogrammatic numbers have a mirrored property; some digits become others when rotated 180 degrees.
Start with the base cases: the smallest strobogrammatic numbers that are either one or two digits long. These are like the building blocks.
Build longer numbers by adding pairs of mirrored digits to the beginning and end of the shorter numbers you've already found. Think of it like adding a frame around a picture.
Keep in mind that '0' cannot be the leading digit for numbers longer than one digit, so avoid adding '0' to both ends in those cases.
Consider the middle digit if the desired number length is odd. The middle digit can only be '0', '1', or '8', since these remain the same when rotated.
Repeat the process of adding digit pairs until you reach the desired length. Each step builds upon the previous, extending the number outwards while maintaining the strobogrammatic property.
The list of numbers generated by this approach will represent all possible combinations since we systematically covered all options.

Code Implementation

def find_strobogrammatic(number_length):
    result = []
    
def extend_strobogrammatic(current_numbers, length):
        if length == 0:
            result.extend(current_numbers)
            return

        new_numbers = []
        strobogrammatic_pairs = [('0', '0'), ('1', '1'), ('6', '9'), ('8', '8'), ('9', '6')]

        for number in current_numbers:
            for pair in strobogrammatic_pairs:
                # Prevent leading zero if not single digit
                if length == number_length and pair[0] == '0' and length > 1:
                    continue
                new_numbers.append(pair[0] + number + pair[1])
        extend_strobogrammatic(new_numbers, length - 2)

    if number_length % 2 == 0:
        extend_strobogrammatic([''], number_length)
    else:
        # Middle digit must be 0, 1 or 8 if odd length
        extend_strobogrammatic(['0', '1', '8'], number_length - 1)

    return result

def find_strobogrammatic_number_ii(number_length):
    # Generate all numbers of desired length
    all_numbers = find_strobogrammatic(number_length)
    return all_numbers

Big(O) Analysis

Time Complexity

O(5^(n/2)) – The algorithm generates strobogrammatic numbers of length n by recursively extending shorter numbers. The base cases (n=1 or n=2) take constant time. However, for each existing strobogrammatic number of length k, we try to extend it with pairs of digits. There are approximately 5 possible pairs (11, 69, 88, 96, 00, with special handling for leading zeros). Since we are effectively growing the number from the middle outwards, the recursion depth will be roughly n/2. Thus the number of strobogrammatic numbers grows roughly proportional to 5^(n/2). Therefore, the time complexity is approximately O(5^(n/2)).

Space Complexity

O(N) – The algorithm builds strobogrammatic numbers of length N by extending shorter numbers. It stores intermediate results in a list (or similar data structure) to hold the generated numbers at each step. In the worst case, we might need to store all possible strobogrammatic numbers of length up to N. The number of such numbers grows exponentially with N, but the depth of the recursion (or the number of iterations in an iterative approach that simulates recursion) is directly proportional to N. Therefore, the auxiliary space required primarily stems from storing these intermediate strobogrammatic numbers, leading to a space complexity of O(N) due to the storage of intermediate lists of numbers of lengths up to N.

Edge Cases

Case	How to Handle
Input n is 0	Return an empty list since a strobogrammatic number must have at least one digit.
Input n is 1	Return the list [0, 1, 8] as these are the only single-digit strobogrammatic numbers.
Input n is 2	Return the list [11, 69, 88, 96] (excluding 00).
Leading zero for n > 1	Avoid constructing numbers starting with zero except for the single digit case.
Integer overflow with large n	String representation avoids potential integer overflow, and the problem constraints typically limit n to a reasonable size.
n is a large even number	The recursive approach explores all possibilities, but can be optimized with memoization to avoid redundant calculations.
n is a large odd number	The recursive approach builds upon the center digit (0, 1, or 8) and proceeds as with even numbers.
No valid strobogrammatic number exists (e.g., n < 0)	Handle invalid inputs by returning an empty list, ensuring the code gracefully handles them.

Input n is 0

How to Handle:

Return an empty list since a strobogrammatic number must have at least one digit.

Input n is 1

How to Handle:

Return the list [0, 1, 8] as these are the only single-digit strobogrammatic numbers.

Input n is 2

How to Handle:

Return the list [11, 69, 88, 96] (excluding 00).

Leading zero for n > 1

How to Handle:

Avoid constructing numbers starting with zero except for the single digit case.

Integer overflow with large n

How to Handle:

String representation avoids potential integer overflow, and the problem constraints typically limit n to a reasonable size.

n is a large even number

How to Handle:

The recursive approach explores all possibilities, but can be optimized with memoization to avoid redundant calculations.

n is a large odd number

How to Handle:

The recursive approach builds upon the center digit (0, 1, or 8) and proceeds as with even numbers.

No valid strobogrammatic number exists (e.g., n < 0)

How to Handle:

Handle invalid inputs by returning an empty list, ensuring the code gracefully handles them.

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:

Given the integer 'n', representing the length of the strobogrammatic numbers, what is the maximum value of 'n'?
Should the generated strobogrammatic numbers be represented as strings or integers?
Are leading zeros allowed in the strobogrammatic numbers generated (except for the single digit '0' when n=1)?
If n is 0, should I return an empty list, or is that an invalid input?
Is there a specific ordering required for the generated strobogrammatic numbers (e.g., lexicographical)? If multiple valid solutions exist, do you require a specific order?

Brute Force Solution

Approach

We are looking for special numbers that look the same when turned upside down. The brute force method tries every possible combination of digits to find these numbers by building them one by one.

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

Start by considering all possible single-digit numbers.
Check if each of these single-digit numbers is strobogrammatic (looks the same upside down).
If we need to create longer numbers, consider all possible two-digit numbers, then three-digit numbers, and so on.
For each number we create, check if it is strobogrammatic.
If the number is strobogrammatic, keep it. If not, discard it.
Repeat this process until we have considered all numbers of the required length.
Finally, list all the strobogrammatic numbers that we found.

Code Implementation

def find_all_strobogrammatic_numbers_brute_force(number_length):
    strobogrammatic_pairs = [('0', '0'), ('1', '1'), ('6', '9'), ('8', '8'), ('9', '6')]

    def is_strobogrammatic(number_string):
        left_index = 0
        right_index = len(number_string) - 1
        while left_index <= right_index:
            if (number_string[left_index], number_string[right_index]) in strobogrammatic_pairs:
                left_index += 1
                right_index -= 1
            else:
                return False
        return True

    def generate_numbers(current_length, max_length):
        if current_length > max_length:
            return []

        if current_length == max_length:
            if current_length == 1:
                return ['0', '1', '8']
            return []

        if current_length == 1:
            result = ['0', '1', '8']
        else:
            result = [str(digit) for digit in range(10)]

        strobogrammatic_numbers = []
        for number in result:
            if len(number) == max_length and number[0] == '0':
                continue

            if is_strobogrammatic(number):
                strobogrammatic_numbers.append(number)

        for length in range(2, max_length + 1):
            new_numbers = []
            for first_digit in range(10):
                for last_digit in range(10):
                    new_number = str(first_digit) + str(last_digit)
                    if len(new_number) == length and new_number[0] == '0':
                        continue

                    if is_strobogrammatic(new_number):
                        strobogrammatic_numbers.append(new_number)

            for current_number in generate_numbers(length, max_length):
                if is_strobogrammatic(current_number):
                    strobogrammatic_numbers.append(current_number)

        return strobogrammatic_numbers

    all_possible_numbers = []
    for length_of_number in range(1, number_length + 1):
        all_numbers_of_length = [''.join(combination) for combination in product('0123456789', repeat=length_of_number)]

        for number_string in all_numbers_of_length:
            # Exclude numbers starting with zero if length > 1
            if len(number_string) > 1 and number_string[0] == '0':
                continue

            # Check if the number is strobogrammatic and append if it is
            if is_strobogrammatic(number_string):
                all_possible_numbers.append(number_string)

    from itertools import product

    strobogrammatic_numbers_final = []
    for length in range(1, number_length + 1):
        # Iterate through all possible digit combinations.
        all_combinations = [''.join(combination) for combination in product('0123456789', repeat=length)]

        for number_string in all_combinations:
            if len(number_string) > 1 and number_string[0] == '0':
                continue

            #Filter out any numbers that are not strobogrammatic
            if is_strobogrammatic(number_string):
                strobogrammatic_numbers_final.append(number_string)

    result = []
    for number_string in strobogrammatic_numbers_final:

        if len(number_string) == number_length:
             #Only return the numbers that match the target number_length
            result.append(number_string)

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Recognize that strobogrammatic numbers have a mirrored property; some digits become others when rotated 180 degrees.
Start with the base cases: the smallest strobogrammatic numbers that are either one or two digits long. These are like the building blocks.
Build longer numbers by adding pairs of mirrored digits to the beginning and end of the shorter numbers you've already found. Think of it like adding a frame around a picture.
Keep in mind that '0' cannot be the leading digit for numbers longer than one digit, so avoid adding '0' to both ends in those cases.
Consider the middle digit if the desired number length is odd. The middle digit can only be '0', '1', or '8', since these remain the same when rotated.
Repeat the process of adding digit pairs until you reach the desired length. Each step builds upon the previous, extending the number outwards while maintaining the strobogrammatic property.
The list of numbers generated by this approach will represent all possible combinations since we systematically covered all options.

Code Implementation

def find_strobogrammatic(number_length):
    result = []
    
def extend_strobogrammatic(current_numbers, length):
        if length == 0:
            result.extend(current_numbers)
            return

        new_numbers = []
        strobogrammatic_pairs = [('0', '0'), ('1', '1'), ('6', '9'), ('8', '8'), ('9', '6')]

        for number in current_numbers:
            for pair in strobogrammatic_pairs:
                # Prevent leading zero if not single digit
                if length == number_length and pair[0] == '0' and length > 1:
                    continue
                new_numbers.append(pair[0] + number + pair[1])
        extend_strobogrammatic(new_numbers, length - 2)

    if number_length % 2 == 0:
        extend_strobogrammatic([''], number_length)
    else:
        # Middle digit must be 0, 1 or 8 if odd length
        extend_strobogrammatic(['0', '1', '8'], number_length - 1)

    return result

def find_strobogrammatic_number_ii(number_length):
    # Generate all numbers of desired length
    all_numbers = find_strobogrammatic(number_length)
    return all_numbers

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input n is 0	Return an empty list since a strobogrammatic number must have at least one digit.
Input n is 1	Return the list [0, 1, 8] as these are the only single-digit strobogrammatic numbers.
Input n is 2	Return the list [11, 69, 88, 96] (excluding 00).
Leading zero for n > 1	Avoid constructing numbers starting with zero except for the single digit case.
Integer overflow with large n	String representation avoids potential integer overflow, and the problem constraints typically limit n to a reasonable size.
n is a large even number	The recursive approach explores all possibilities, but can be optimized with memoization to avoid redundant calculations.
n is a large odd number	The recursive approach builds upon the center digit (0, 1, or 8) and proceeds as with even numbers.
No valid strobogrammatic number exists (e.g., n < 0)	Handle invalid inputs by returning an empty list, ensuring the code gracefully handles them.

Input n is 0

How to Handle:

Return an empty list since a strobogrammatic number must have at least one digit.

Input n is 1

How to Handle:

Return the list [0, 1, 8] as these are the only single-digit strobogrammatic numbers.

Input n is 2

How to Handle:

Return the list [11, 69, 88, 96] (excluding 00).

Leading zero for n > 1

How to Handle:

Avoid constructing numbers starting with zero except for the single digit case.

Integer overflow with large n

How to Handle:

String representation avoids potential integer overflow, and the problem constraints typically limit n to a reasonable size.

n is a large even number

How to Handle:

The recursive approach explores all possibilities, but can be optimized with memoization to avoid redundant calculations.

n is a large odd number

How to Handle:

The recursive approach builds upon the center digit (0, 1, or 8) and proceeds as with even numbers.

No valid strobogrammatic number exists (e.g., n < 0)

How to Handle:

Handle invalid inputs by returning an empty list, ensuring the code gracefully handles them.