Strobogrammatic number
For the given length n, find all n-length Strobogrammatic numbers.
Strobogrammatic Number is a number whose numeral is rotationally symmetric so that it appears the same when rotated 180 degrees. In other words, Strobogrammatic Number appears the same right-side up and upside down.
0 after 180° rotation : (0 → 0)
1 after 180° rotation : (1 → 1)
8 after 180° rotation : (8 → 8)
6 after 180° rotation : (6 → 9)
9 after 180° rotation : (9 → 6)
Examples :
Input : n = 2
Output : 88 11 96 69Input : n = 4
Output : 8008 1001 9006 6009 8888 1881 9886 6889 8118 1111
9116 6119 8968 1961 9966 6969 8698 1691 9696 6699
Code:
Below is the Python3 implementation :
#include <bits/stdc++.h>
using namespace std;
vector<string> numdef(int n, int length)
{
vector<string> result;
if (n == 0){
result.push_back("");
return result;
}
if (n == 1) {
result.push_back("1");
result.push_back("0");
result.push_back("8");
return result;
}
vector<string> middles = numdef(n - 2, length);
for (string middle : middles) {
if (n != length)
result.push_back("0" + middle + "0");
result.push_back("8" + middle + "8");
result.push_back("1" + middle + "1");
result.push_back("9" + middle + "6");
result.push_back("6" + middle + "9");
}
return result;
}
vector<string> strobogrammatic_num(int n)
{
vector<string> result = numdef(n, n);
return result;
}
int main()
{
// Print all Strobogrammatic numbers for n = 2
for (string num : strobogrammatic_num(2))
cout << num << " ";
return 0;
}
// code contributed by Oprix
import java.util.*;
class GFG {
// definition function
static ArrayList<String> numdef(int n, int length) {
ArrayList<String> result = new ArrayList<String>();
if (n == 0){
result.add("");
return result;
}
if (n == 1) {
result.add("1");
result.add("0");
result.add("8");
return result;
}
ArrayList<String> middles = numdef(n - 2, length);
for (String middle : middles) {
if (n != length)
result.add("0" + middle + "0");
result.add("8" + middle + "8");
result.add("1" + middle + "1");
result.add("9" + middle + "6");
result.add("6" + middle + "9");
}
return result;
}
// strobogrammatic function
static ArrayList<String> strobogrammatic_num(int n) {
ArrayList<String> result = numdef(n, n);
return result;
}
// Driver Code
public static void main(String[] args) {
// Print all Strobogrammatic numbers for n = 2
for (String num : strobogrammatic_num(2))
System.out.print(num + " ");
}
}
// This code is contributed by Oprix
# Python program to print all
# Strobogrammatic numbers of length n
# Strobogrammatic function
def strobogrammatic_num(n):
result = numdef(n, n)
return result
# Definition function
def numdef(n, length):
if n == 0: return [""]
if n == 1: return ["1", "0", "8"]
middles = numdef(n - 2, length)
result = []
for middle in middles:
if n != length:
result.append("0" + middle + "0")
result.append("8" + middle + "8")
result.append("1" + middle + "1")
result.append("9" + middle + "6")
result.append("6" + middle + "9")
return result
# Driver Code
if __name__ == '__main__':
# Print all Strobogrammatic numbers for n = 2
print(strobogrammatic_num(4))
using System;
using System.Collections.Generic;
class GFG
{
// definition function
static List<string> numdef(int n, int length)
{
List<string> result = new List<string>();
if (n == 0)
{
result.Add("");
return result;
}
if (n == 1) {
result.Add("1");
result.Add("0");
result.Add("8");
return result;
}
List<string> middles = numdef(n - 2, length);
foreach (string middle in middles)
{
if (n != length)
result.Add("0" + middle + "0");
result.Add("8" + middle + "8");
result.Add("1" + middle + "1");
result.Add("9" + middle + "6");
result.Add("6" + middle + "9");
}
return result;
}
// strobogrammatic function
static List<string> strobogrammatic_num(int n)
{
List<string> result = numdef(n, n);
return result;
}
// Driver Code
public static void Main(string[] args)
{
// Print all Strobogrammatic numbers for n = 2
foreach (string num in strobogrammatic_num(2))
Console.Write(num + " ");
}
}
// This code is contributed by Oprix
// JavaScript program to print all
// Strobogrammatic number of length n
// strobogrammatic function
function strobogrammatic_num(n) {
let result = numdef(n, n);
return result;
}
// definition function
function numdef(n, length) {
if (n == 0) return [""];
if (n == 1) return ["1", "0", "8"];
let middles = numdef(n - 2, length);
let result = [];
for (var middle of middles) {
if (n != length)
result.push("0" + middle + "0");
result.push("8" + middle + "8");
result.push("1" + middle + "1");
result.push("9" + middle + "6");
result.push("6" + middle + "9");
}
return result;
}
// Driver Code
// Print all Strobogrammatic
// numbers for n = 2
console.log(strobogrammatic_num(2));
OUTPUT
88 11 96 69
Time Complexity: O(5^n)
Auxiliary Space: O(5^n)
Reference : https://en.wikipedia.org/wiki/Strobogrammatic_number