| 29 November 2024 | Challenge 297 |
Semi-Permutational Contiguities
Task 1: Contiguous Array
Submitted by: Mohammad Sajid Anwar
You are given an array of binary numbers, @binary.
Write a script to return the maximum length of a contiguous subarray with an equal number of 0 and 1.
Example 1
Input: @binary = (1, 0)
Output: 2
(1, 0) is the longest contiguous subarray with an equal number of 0 and 1.
Example 2
Input: @binary = (0, 1, 0)
Output: 2
(1, 0) or (0, 1) is the longest contiguous subarray with an equal number of 0 and 1.
Example 3
Input: @binary = (0, 0, 0, 0, 0)
Output: 0
Example 4
Input: @binary = (0, 1, 0, 0, 1, 0)
Output: 4
Solution
Though the task states
an array of binary numbers
I’ll assume the array contains only zeroes and ones as elements, not binary numbers like 10011.
This task can be solved in \(\mathcal{O}(N)\) operations.
We may turn all zeroes in the array @binary to -1, resulting in a new array @z.
If a contiguous subarray of @binary contains an equal number of zeroes and ones, then the same subarray of @z has a sum of zero and vice versa.
Building an array @s as the cumulative sums over @z:
$s[0] = 0
$s[$i] = $s[$i - 1] + $z[$i - 1]
The sum over the subarray @z[$p .. $q - 1] (having a length of $q - $p) equals $s[$q] - $s[$p].
A subarray having a sum of zero thus can be identified by the positions of equal elements within @s.
In a hash %firstlast we now record the indices of the first and last appearance for every element of @s.
Then we take the maximum difference over the (first, last) pairs as the requested result.
Though the arrays @z and @s are helpful when describing the procedure, they are actually not needed.
All the given steps may be performed within a single loop without storing the values in @z and @s.
The last index doesn’t need to be stored, neither.
This may be implemented as:
use strict;
use warnings;
sub max_contig {
my %first = (0 => 0);
my ($max, $s, $i) = 0;
for my $b (@_) {
$s += $b || -1;
$i++;
$first{$s} = $i, next unless exists $first{$s};
my $len = $i - $first{$s};
$max = $len if $len > $max;
}
$max;
}
See the full solution to task 1.
Task 2: Semi-Ordered Permutation
Submitted by: Mohammad Sajid Anwar
You are given permutation of $n integers, @ints.
Write a script to find the minimum number of swaps needed to make the @ints a semi-ordered permutation.
A permutation is a sequence of integers from 1 to n of length n containing each number exactly once.
A permutation is called semi-ordered if the first number is 1 and the last number equals n.
You are ONLY allowed to pick adjacent elements and swap them.
Example 1
Input: @ints = (2, 1, 4, 3)
Output: 2
Swap 2 <=> 1 => (1, 2, 4, 3)
Swap 4 <=> 3 => (1, 2, 3, 4)
Example 2
Input: @ints = (2, 4, 1, 3)
Output: 3
Swap 4 <=> 1 => (2, 1, 4, 3)
Swap 2 <=> 1 => (1, 2, 4, 3)
Swap 4 <=> 3 => (1, 2, 3, 4)
Example 3
Input: @ints = (1, 3, 2, 4, 5)
Output: 0
Already a semi-ordered permutation.
Solution
Let the index of 1 be $min and the index of n be $max.
We need $min swaps to move 1 to position 0 and we need n - 1 - $max swaps to move n to position n - 1.
In case $max is smaller than $min, we save one swap when exchanging 1 with n.
Using PDL we may find $min and $max simultaneously with a single call to minmaximum.
use strict;
use warnings;
use PDL;
sub semi_ordered {
my (undef, undef, $min, $max) = minmaximum long @_;
$min + $#_ - $max - ($max < $min);
}
See the full solution to task 2.
If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.