Task 1: Arrange Binary
You are given a list of binary digits (0 and 1) and a positive integer, $n.
Write a script to return true if you can re-arrange the list by replacing at least $n digits with 1 so that no two consecutive digits are 1, otherwise return false.
Example 1
Input: @digits = (1, 0, 0, 0, 1), $n = 1
Output: true
Re-arranged list: (1, 0, 1, 0, 1)
Example 2
Input: @digits = (1, 0, 0, 0, 1), $n = 2
Output: false
Logic
The maximum number of 1s that can be placed in an array of length L without any two being adjacent is ceil(L/2) = (L+1)//2. Count the existing 1s, add n, and check if the total fits within this maximum.
Perl Solution
ch-1.pl
#!/usr/bin/env perl
use strict;
use warnings;
use Test::More;
sub can_arrange_binary {
my ($digits_ref, $n) = @_;
my $ones_count = grep { $_ == 1 } @$digits_ref;
my $max_possible_ones = int((scalar(@$digits_ref) + 1) / 2);
my $total_ones = $ones_count + $n;
return $total_ones <= $max_possible_ones;
}
ok(can_arrange_binary([1,0,0,0,1], 1), 'Example 1');
ok(!can_arrange_binary([1,0,0,0,1], 2), 'Example 2');
Python Solution
ch-1.py
def can_arrange_binary(digits: list[int], n: int) -> bool:
ones_count = sum(digits)
max_possible_ones = (len(digits) + 1) // 2
total_ones = ones_count + n
return total_ones <= max_possible_ones
Task 2: Maximum Average
You are given an array of integers, @ints, and an integer $n.
Write a script to find the contiguous subarray of length $n with the maximum average. Return the average.
Example 1
Input: @ints = (1, 12, -5, -6, 50, 3), $n = 4
Output: 12.75
Subarray: (12, -5, -6, 50)
Average: (12 - 5 - 6 + 50) / 4 = 12.75
Example 2
Input: @ints = (5), $n = 1
Output: 5
Logic
Use a sliding window of size n. Compute the sum of the initial window, then slide it across the array: add the new element entering the window and subtract the one leaving. Track the maximum sum seen, then divide by n for the average. O(n) time.
Perl Solution
ch-2.pl
#!/usr/bin/env perl
use strict;
use warnings;
use Test::More;
sub find_max_average {
my ($nums_ref, $n) = @_;
die "Invalid input" if !@$nums_ref || $n > scalar(@$nums_ref);
my $window_sum = 0;
$window_sum += $_ for @$nums_ref[0 .. $n-1];
my $max_sum = $window_sum;
for my $i ($n .. scalar(@$nums_ref) - 1) {
$window_sum += $nums_ref->[$i] - $nums_ref->[$i - $n];
$max_sum = $window_sum if $window_sum > $max_sum;
}
return $max_sum / $n;
}
is(find_max_average([1,12,-5,-6,50,3], 4), 12.75, 'Example 1');
is(find_max_average([5], 1), 5, 'Example 2');
Python Solution
ch-2.py
def find_max_average(nums: list[int], n: int) -> float:
if not nums or n > len(nums):
raise ValueError("Invalid input")
window_sum = sum(nums[:n])
max_sum = window_sum
for i in range(n, len(nums)):
window_sum += nums[i] - nums[i - n]
max_sum = max(max_sum, window_sum)
return max_sum / n