[Solved] Strobogrammatic Number ll Contest Problem

Strobogrammatic Number ll: Given a length ‘N’, you need to find all the strobogrammatic numbers of length ‘N’.

A strobogrammatic number is a number that looks the same when rotated by 180.

In other words, a number that on rotating right side up and upside down appears the same is a strobogrammatic number.

‘986’ is a strobogrammatic number because on rotating ‘986’ by 180 degrees, ‘986’ will be obtained.

For Example:

If N = 2, all the strobogrammatic numbers of length = 2 are “11”, “88”, “69”, “96”.

Strobogrammatic Number ll Contest Problem

Input Format:

The first line contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains a single integer denoting ‘N’.

Output Format:

For each test case, print space-separated strings denoting strobogrammatic numbers of the given length.

Print the output of each test case in a separate line.

Note:

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 7

Where ‘T’ is the number of test cases, and ‘N’ is the given length.

Time Limit: 1 sec

Sample Input 1:

2
3
1

Sample Output 1:

101 111 181 609 619 689 808 818 888 906 916 986 
0 1 8 

Explanation For Sample Input 1:

Test Case 1: All the possible Strobogrammatic numbers of length = 3 are “101”, “111”, “181”, “609”, “619”, “689”, “808”, “818”, “906”, “916”, “986”.

Test Case 2: Strobogrammatic numbers of length = 1 are “0”, “1”, and “8”.

Sample Input 2:

2
4
2

Sample Output 2:

1001 1111 1691 1881 1961 6009 6119 6699 6889 6969 8008 8118 8698 8888 8968 9006 9116 9696 9886 9966 
11 69 88 96 

Explanation For Sample Input 2:

Test Case 1: All the possible Strobogrammatic numbers of length = 4 are printed.

Test Case 2: All the possible Strobogrammatic numbers of length = 2 are printed.

Solution

Recursion

Approach: Out of all the 10 digits, 0,1,6,8,9 will give a valid digit when rotated upside down(top part turned to bottom).

After rotating upside down digits will be-

0 -> 0

1 -> 1

6 -> 9

8 -> 8

9 -> 6

So We have to form numbers using only 0,1,6,8,9.

The basic idea is that we will reduce the problem into small problems. We will recursively solve the problem for length = length – 2. And then add digits out of (0,1,6,8,9) at the starting and the corresponding digits (0,1,9,8,6) at the end.

Recursion will be stopped when len = 0 and len – 1.

If len = 0, we will return an empty string and in case len = 1, we will return three strings “1”, “0”, “8” as these are the strobogrammatic numbers with pen = 1.

Let us understand this with an example for N = 4.

Algorithm:

1. Let ‘findStrobogrammatic’ be the recursive function that will return an array of strings denoting all the strobogrammatic numbers.
2. The recursive function will take ‘N’, denting the length given, and ‘len’ initialized as ‘N’.
3. Base Cases
   • If ‘N’ is ‘0’, return the empty string.
   • If ‘N’ is ‘1’ return “1”, “0”, “8”.
4. Recursively call for ‘N’ and ‘len-2’ and store the result of this recursive call in an array of strings “prev”.
5. Initialize an array of strings “res” to store the strings after adding digits at start and end of the strings in “prev”.
6. Run a loop i: 0 to (size of “prev” – 1) to traverse all the strings in “prev”.
   • If N is not equal to len, add “0” + prev[ i ] “0”to “res”.
   • Add “1” + prev[ i ] +“1” to “res”.
   • Add “6” + prev[ i ] +“9” to “res”.
   • Add “8” + prev[ i ] +“8” to “res”.
   • Add “9” + prev[ i ] +“6” to “res”
7. Return “res”.

Time Complexity

O(5^N), where ‘N’ is the given length.

Since for every pair of digits in the strobogrammatic number, we have 5 choices(0, 1, 6, 8, 9), and we are iterating over each of them. Therefore, the time complexity is O(5^N).

Space Complexity

O(5^N), where ‘N’ is the given length.

Since for every pair of digits in the strobogrammatic number, we have 5 choices(0, 1, 6, 8, 9), and there would be ‘N/2’ pairs. So there will be approximately  5^(N) strobogrammatic numbers of length ‘N’. Therefore, space complexity is O(5^N).

/*
    Time Complexity  : O(5^N)
    Space Complexity : O(5^N)
    
    Where 'N' is the given length.
*/

import java.util.ArrayList;

public class Solution {

    public static ArrayList<String> findStrobogrammaticHelper(int n, int len){

        ArrayList<String> res = new ArrayList<String>();

        // If len = 0, return empty string.
        if (len == 0) {
            res.add("");
            return res;
        }

        if (len == 1) {
            res.add("0");
            res.add("1");
            res.add("8");
            return res;
        }

        // Recursively call for len = len - 2.
        ArrayList<String> prev = findStrobogrammaticHelper(n, len - 2);

        // Iterate through all strings in "prev".
        for (int i = 0; i < prev.size(); i++) {

            // Add digits around string prev[i].
            if (len != n) {
                res.add("0" + prev.get(i) + "0");
            }

            res.add("1" + prev.get(i) + "1");
            res.add("6" + prev.get(i) + "9");
            res.add("8" + prev.get(i) + "8");
            res.add("9" + prev.get(i) + "6");
        }

        return res;
    }

    public static ArrayList<String> findStrobogrammatic(int n) {
        // Recursive function to find all strobogrammatic numbers.
        ArrayList<String> ans = findStrobogrammaticHelper(n, n);

        return ans;
    }
}

/*
    Time Complexity  : O(5^N)
    Space Complexity : O(5^N)
    
    Where 'N' is the given length.
*/

vector < string > findStrobogrammaticHelper(int n, int len) {

    // If len = 0, return empty string.
    if (len == 0) {
        return vector < string > ({ "" });
    }

    if (len == 1) {
        return vector < string > ({"0", "1", "8" });
    }

    // Recursively call for len = len - 2.
    vector < string > prev = findStrobogrammaticHelper(n, len - 2);

    // Initialize vector of strings to store resulting strings.
    vector < string > res;

    // Iterate through all strings in "prev".
    for (int i = 0; i < prev.size(); i++) {

        // Add digits around string prev[i].
        if (len != n) {
            res.push_back("0" + prev[i] + "0");
        }

        res.push_back("1" + prev[i] + "1");
        res.push_back("6" + prev[i] + "9");
        res.push_back("8" + prev[i] + "8");
        res.push_back("9" + prev[i] + "6");
    }

    return res;
}

vector < string > findStrobogrammatic(int n) {
    // Recursive function to find all strobogrammatic numbers.
    vector < string > ans = findStrobogrammaticHelper(n, n);

    return ans;
}

'''
    Time Complexity  : O(5^N)
    Space Complexity : O(5^N)
    
    Where 'N' is the given length.
'''

def findStrobogrammaticHelper( n, lenn):

    # If len = 0, return empty string.
    if (lenn == 0):    
        return [""]
    
    if (lenn == 1):
        return ['0','1','8']
    
    # Recursively call for len = len - 2.
    prev = findStrobogrammaticHelper(n, lenn - 2)
    
    # Initialize vector of strings to store resulting strings.
    res=[]
    
    # Iterate through all strings in "prev".
    for i in range(len(prev)):
        
        # Add digits around string prev[i].
        if (lenn != n):
            res.append("0" + prev[i] + "0")
        
        res.append("1" + prev[i] + "1")
        res.append("6" + prev[i] + "9")
        res.append("8" + prev[i] + "8")
        res.append("9" + prev[i] + "6")
    
    return res


def findStrobogrammatic(n):
    # Recursive function to find all strobogrammatic numbers.
    ans = findStrobogrammaticHelper(n, n)
    return ans

Happy Learning – If you require any further information, feel free to contact me.