Strobogrammatic Number ll

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
20 upvotes
Asked in company
Google inc

Problem statement

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”.
Detailed explanation ( Input/output format, Notes, Images )
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.
Hint

Can you try to divide your problem into smaller sub-problems?

Approaches (1)
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).

Code Solution
(100% EXP penalty)
Strobogrammatic Number ll
Full screen
Console