The Weekly Challenge 069

Strobogrammatic Number and Binary String Generator

Solutions on GitHub

Task 1: Strobogrammatic Number

Find all strobogrammatic numbers between A and B (numbers that look the same when rotated 180 degrees).

Example Output

Range: [50, 100] Output: [69, 88, 96]

Logic

A strobogrammatic number contains valid pairs (0,0), (1,1), (6,9), (8,8), (9,6) symmetrically placed from outer ends.

Perl Solution

ch-1.pl

sub is_strobogrammatic { my ($n) = @_; my %map = ('0'=>'0', '1'=>'1', '6'=>'9', '8'=>'8', '9'=>'6'); my @digits = split //, $n; my ($i, $j) = (0, $#digits); while ($i <= $j) { return 0 unless exists $map{$digits[$i]} && $map{$digits[$i]} eq $digits[$j]; $i++; $j--; } return 1; }

Python Solution

ch-1.py

def is_strobogrammatic(n: str) -> bool: mapping = {'0': '0', '1': '1', '6': '9', '8': '8', '9': '6'} i, j = 0, len(n) - 1 while i <= j: if n[i] not in mapping or mapping[n[i]] != n[j]: return False i += 1; j -= 1 return True

Task 2: Binary String Generator

Generate n-th binary string S_n formed by S_n = S_{n-1} + '1' + invert(reverse(S_{n-1})).

Example Output

S1 = '0', S2 = '011', S3 = '0111001'

Logic

Recursively generate S_{n-1}, invert and reverse it, and concatenate with '1'.

Perl Solution

ch-2.pl

sub generate_string { my ($n) = @_; return '0' if $n == 1; my $prev = generate_string($n - 1); my $inv_rev = join '', map { $_ eq '0' ? '1' : '0' } reverse split //, $prev; return $prev . '1' . $inv_rev; }

Python Solution

ch-2.py

def generate_string(n: int) -> str: if n == 1: return '0' prev = generate_string(n - 1) inv_rev = ''.join('1' if c == '0' else '0' for c in reversed(prev)) return prev + '1' + inv_rev