Task 1: Rearrange Binary String
Simultaneously replace all occurrences of "01" with "10" until no "01" remains. Return the total number of steps.
Example Output
Input: $str = "00011"
Output: 4
Input: $str = "010101"
Output: 3
Logic
Simulate the replacement steps in a loop, replacing all occurrences of '01' with '10' in each iteration until no '01' substring is present.
Perl Solution
ch-1.pl
sub rearrange_binary_string ($str) {
my $steps = 0;
while ( $str =~ /01/ ) {
$str =~ s/01/10/g;
$steps++;
}
return $steps;
}
Python Solution
ch-1.py
def rearrange_binary_string(s: str) -> int:
"""Return number of steps to replace all '01' with '10'."""
steps = 0
while "01" in s:
s = s.replace("01", "10")
steps += 1
return steps
Task 2: Atoms Count
Given a chemical formula with nested parentheses and multipliers, count each atom and return the result sorted alphabetically, omitting multiplier 1.
Example Output
Input: $formula = "Mg3(PO4)2"
Output: "Mg3O8P2"
Input: $formula = "((N2O)3(H2O)2)2"
Output: "H8N12O10"
Logic
Maintain a stack of atom count maps. Push a new map upon '(', and upon ')' multiply counts in the popped map by the following number and merge into the parent map. Sort atoms alphabetically and concatenate.
Perl Solution
ch-2.pl
sub count_atoms ($formula) {
my @stack = ( {} );
my $len = length($formula);
my $i = 0;
while ( $i < $len ) {
my $char = substr( $formula, $i, 1 );
if ( $char eq '(' ) {
push @stack, {};
$i++;
}
elsif ( $char eq ')' ) {
$i++;
my $start = $i;
while ( $i < $len && substr( $formula, $i, 1 ) =~ /\d/ ) {
$i++;
}
my $mult_str = substr( $formula, $start, $i - $start );
my $mult = length($mult_str) > 0 ? int($mult_str) : 1;
my $top = pop @stack;
for my $elem ( keys %$top ) {
$stack[-1]->{$elem} = ( $stack[-1]->{$elem} // 0 ) + $top->{$elem} * $mult;
}
}
elsif ( $char =~ /[A-Z]/ ) {
my $start_elem = $i;
$i++;
while ( $i < $len && substr( $formula, $i, 1 ) =~ /[a-z]/ ) {
$i++;
}
my $elem = substr( $formula, $start_elem, $i - $start_elem );
my $start_num = $i;
while ( $i < $len && substr( $formula, $i, 1 ) =~ /\d/ ) {
$i++;
}
my $mult_str = substr( $formula, $start_num, $i - $start_num );
my $mult = length($mult_str) > 0 ? int($mult_str) : 1;
$stack[-1]->{$elem} = ( $stack[-1]->{$elem} // 0 ) + $mult;
}
else {
die "Unexpected character '$char' at position $i";
}
}
my $counts = $stack[0];
my $result = '';
for my $elem ( sort keys %$counts ) {
$result .= $elem;
$result .= $counts->{$elem} if $counts->{$elem} > 1;
}
return $result;
}
Python Solution
ch-2.py
def count_atoms(formula: str) -> str:
"""Parse chemical formula and return sorted element counts."""
stack: list[dict[str, int]] = [defaultdict(int)]
i = 0
n = len(formula)
while i < n:
char = formula[i]
if char == "(":
stack.append(defaultdict(int))
i += 1
elif char == ")":
i += 1
start = i
while i < n and formula[i].isdigit():
i += 1
mult_str = formula[start:i]
mult = int(mult_str) if mult_str else 1
top = stack.pop()
for elem, count in top.items():
stack[-1][elem] += count * mult
elif char.isupper():
start_elem = i
i += 1
while i < n and formula[i].islower():
i += 1
elem = formula[start_elem:i]
start_num = i
while i < n and formula[i].isdigit():
i += 1
mult_str = formula[start_num:i]
mult = int(mult_str) if mult_str else 1
stack[-1][elem] += mult
else:
raise ValueError(f"Unexpected character '{char}' at index {i}")
counts = stack[0]
result_parts: list[str] = []
for elem in sorted(counts.keys()):
result_parts.append(elem)
if counts[elem] > 1:
result_parts.append(str(counts[elem]))
return "".join(result_parts)