w3resource

Python: Get all strobogrammatic numbers that are of length n


Strobogrammatic Numbers

Write a Python program to get all strobogrammatic numbers that are of length n.

A strobogrammatic number is a number whose numeral is rotationally symmetric, so that it appears the same when rotated 180 degrees. In other words, the numeral looks the same right-side up and upside down (e.g., 69, 96, 1001).

For example,
Given n = 2, return ["11", "69", "88", "96"].
Given n = 3, return ['818', '111', '916', '619', '808', '101', '906', '609', '888', '181', '986', '689']

Visual Presentation:

Python:  Get all strobogrammatic numbers that are of length n

Sample Solution:

Python Code:

# Define a function 'gen_strobogrammatic' that generates strobogrammatic numbers of length 'n'.
def gen_strobogrammatic(n):
    """
    :type n: int
    :rtype: List[str]
    """
    # Call the helper function with the given length 'n'.
    result = helper(n, n)
    return result

# Define a helper function 'helper' to recursively generate strobogrammatic numbers.
def helper(n, length):
    # Base case: when 'n' is 0, return an empty string.
    if n == 0:
        return [""]
    # Base case: when 'n' is 1, return the strobogrammatic digits for length 1.
    if n == 1:
        return ["1", "0", "8"]
    # Recursive case: generate strobogrammatic numbers for 'n-2'.
    middles = helper(n-2, length)
    result = []
    # Iterate over the generated middles and create strobogrammatic numbers.
    for middle in middles:
        # If 'n' is not equal to the original length, add "0" on both sides.
        if n != length:
            result.append("0" + middle + "0")
        # Add strobogrammatic numbers with "8" in the middle.
        result.append("8" + middle + "8")
        # Add strobogrammatic numbers with "1" in the middle.
        result.append("1" + middle + "1")
        # Add strobogrammatic numbers with "9" in the first half and "6" in the second half.
        result.append("9" + middle + "6")
        # Add strobogrammatic numbers with "6" in the first half and "9" in the second half.
        result.append("6" + middle + "9")
    return result

# Test the function with different values of 'n' and print the results.
print("n = 2: \n", gen_strobogrammatic(2))
print("n = 3: \n", gen_strobogrammatic(3))
print("n = 4: \n", gen_strobogrammatic(4))

Sample Output:

n = 2: 
 ['88', '11', '96', '69']
n = 3: 
 ['818', '111', '916', '619', '808', '101', '906', '609', '888', '181', '986', '689']
n = 4: 
 ['8008', '1001', '9006', '6009', '8888', '1881', '9886', '6889', '8118', '1111', '9116', '6119', '8968', '1961', '9966', '6969', '8698', '1691', '9696', '6699']

Explanation:

The above Python code generates strobogrammatic numbers of a given length 'n'. Strobogrammatic numbers are those that remain the same when rotated 180 degrees. Here's a brief explanation:

  • The main function is "gen_strobogrammatic(n)", which takes an integer 'n' as input and returns a list of strobogrammatic numbers of length 'n'.
  • The main function calls a helper function "helper(n, length)" to recursively generate strobogrammatic numbers.
  • In the helper function:
    • If 'n' is 0, it returns a list containing an empty string (base case).
    • If 'n' is 1, it returns a list of strobogrammatic digits for length 1 ('1', '0', '8').
    • For 'n' greater than 1, it recursively generates strobogrammatic numbers for 'n-2'.
  • The "helper()" function builds strobogrammatic numbers by adding digits in the middle and considering rotations:
    • If 'n' is not equal to the original length, it adds "0" on both sides.
    • It adds strobogrammatic numbers with "8" in the middle.
    • It adds strobogrammatic numbers with "1" in the middle.
    • It adds strobogrammatic numbers with "9" in the first half and "6" in the second half.
    • It adds strobogrammatic numbers with "6" in the first half and "9" in the second half.
  • The main function returns the result generated by the helper function.
  • The code then tests the gen_strobogrammatic function with different values of 'n' (2, 3, 4) and prints the results.

Flowchart:

Flowchart: Python - Get all strobogrammatic numbers that are of length n

Python Code Editor :

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Write a Python program to get the third side of right angled triangle from two given sides.
Next: Write a Python program to find the median among three given numbers.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.