Task 1: Ones and Zeroes
You are given an array of binary strings, @str, and two integers, $x and $y.
Write a script to return the size of the largest subset of @str such that there are at most $x 0's and $y 1's in the subset.
Example 1
Input: @str = ("10", "0001", "111001", "1", "0")
$x = 5
$y = 3
Output: 4
Largest subset: ("10", "0001", "1", "0")
Example 2
Input: @str = ("10", "1", "0")
$x = 1
$y = 1
Output: 2
Largest subset: ("1", "0")
Logic
This is a 0/1 knapsack problem over two dimensions: zeros and ones. For each string, count its zeros and ones, then update a 2D DP table from high to low so each string is used at most once. dp[i][j] stores the maximum subset size with at most i zeros and j ones.
Perl Solution
ch-1.pl
#!/usr/bin/env perl
use v5.38;
use warnings;
use feature 'signatures';
no warnings 'experimental::signatures';
sub ones_and_zeroes ($x, $y, $strs) {
my @dp;
for my $i (0 .. $x) {
$dp[$i] = [ (0) x ($y + 1) ];
}
for my $s (@$strs) {
my $zeros = ($s =~ tr/0//);
my $ones = length($s) - $zeros;
for (my $i = $x; $i >= $zeros; --$i) {
for (my $j = $y; $j >= $ones; --$j) {
my $candidate = $dp[$i - $zeros][$j - $ones] + 1;
$dp[$i][$j] = $candidate if $candidate > $dp[$i][$j];
}
}
}
return $dp[$x][$y];
}
Python Solution
ch-1.py
def ones_and_zeroes(strs: list[str], x: int, y: int) -> int:
dp = [[0] * (y + 1) for _ in range(x + 1)]
for s in strs:
zeros = s.count("0")
ones = len(s) - zeros
for i in range(x, zeros - 1, -1):
for j in range(y, ones - 1, -1):
dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
return dp[x][y]
Task 2: Step by Step
You are given an array of integers, @ints.
Write a script to find the minimum positive start value such that step by step sum is never less than one.
Example 1
Input: @ints = (-3, 2, -3, 4, 2)
Output: 5
For start value 5:
5 + (-3) = 2
2 + (+2) = 4
4 + (-3) = 1
1 + (+4) = 5
5 + (+2) = 7
Example 2
Input: @ints = (1, 2)
Output: 1
Example 3
Input: @ints = (1, -2, -3)
Output: 5
Logic
Track the running prefix sum and the minimum prefix seen. If the lowest point is min_prefix, the start value must satisfy start + min_prefix >= 1, so the answer is 1 - min_prefix.
Perl Solution
ch-2.pl
#!/usr/bin/env perl
use v5.38;
use warnings;
use feature 'signatures';
no warnings 'experimental::signatures';
sub minimum_start_value ($ints) {
my $sum = 0;
my $min_prefix = 0;
for my $v (@$ints) {
$sum += $v;
$min_prefix = $sum if $sum < $min_prefix;
}
return 1 - $min_prefix;
}
Python Solution
ch-2.py
def minimum_start_value(ints: list[int]) -> int:
prefix = 0
min_prefix = 0
for value in ints:
prefix += value
if prefix < min_prefix:
min_prefix = prefix
return 1 - min_prefix