Task 1: Flip Binary
You are given a binary string. You are allowed to flip characters (0 to 1 or 1 to 0) in one contiguous segment exactly once. Find the segment [L, R] that maximizes the number of 1s in the resulting string.
Example Output
Input: "010"
Output: Max 1s: 2 (Segments: [0, 0], [0, 2], [2, 2])
Logic
Generate all possible pairs of indices L and R. For each pair, flip the contiguous segment between them and count the total number of 1s. Keep track of the maximum count and the corresponding indices.
Perl Solution
ch-1.pl
sub process_all_flips {
my $binary = shift;
my %all_results;
my $max = 0;
my @numbers = split //, $binary;
for my $l_count ( 0 .. scalar(@numbers)-1 ) {
for my $r_count ( $l_count .. scalar(@numbers)-1 ) {
my $inverted = do_flip( $l_count, $r_count, $binary );
my $ones_count = () = $inverted =~ /1/gi;
push @{ $all_results{$ones_count} }, [ $l_count, $r_count ];
$max = $ones_count if $ones_count > $max;
}
}
return $all_results{$max};
}
Python Solution
ch-1.py
class BinFlip:
def process_all_flips(self):
for l_count in range(len(self.to_flip)):
for r_count in range(l_count, len(self.to_flip)):
self.l_count = l_count
self.r_count = r_count
self.current_flip = self.do_flip()
self.process_current()
return self.max_ones, self.all_flips[self.max_ones]
Task 2: Wave Array
Given an array of unique integers, find all permutations that form a wave array. A wave array is an array a where a[0] >= a[1] <= a[2] >= a[3] <= ....
Example Output
Input: [1, 2, 3, 4]
Output: [2, 1, 4, 3], [3, 1, 4, 2], [3, 2, 4, 1], [4, 1, 3, 2], [4, 2, 3, 1]
Logic
Generate all permutations of the array. For each permutation, check if it alternates between decreasing and increasing steps (wave shape).
Perl Solution
ch-2.pl
sub check_wave {
my $perm_ref = shift;
my $direction = 1; # 1 = greater, -1 = smaller
for ( 0 .. scalar(@$perm_ref) - 2 ) {
if ( $direction == 1 ) {
return 0 if $$perm_ref[$_] < $$perm_ref[ $_ + 1 ];
}
else {
return 0 if $$perm_ref[$_] > $$perm_ref[ $_ + 1 ];
}
$direction *= -1;
}
return 1;
}
Python Solution
ch-2.py
class WaveArray:
@property
def check_wave(self):
direction = 1
for seq_count in range(len(self.current_wave)-1):
if direction == 1:
if self.current_wave[seq_count] < self.current_wave[seq_count+1]:
return False
else:
if self.current_wave[seq_count] > self.current_wave[seq_count+1]:
return False
direction *= -1
return True