Last Updated: 18 Apr, 2021

Strobogrammatic Number ll

Moderate

Asked in company

Solve now

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”.

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

Solve now

Approaches

01 Approach

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:

Let ‘findStrobogrammatic’ be the recursive function that will return an array of strings denoting all the strobogrammatic numbers.
The recursive function will take ‘N’, denting the length given, and ‘len’ initialized as ‘N’.
Base Cases
- If ‘N’ is ‘0’, return the empty string.
- If ‘N’ is ‘1’ return “1”, “0”, “8”.
Recursively call for ‘N’ and ‘len-2’ and store the result of this recursive call in an array of strings “prev”.
Initialize an array of strings “res” to store the strings after adding digits at start and end of the strings in “prev”.
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”
Return “res”.

Solve now