The Weekly Challenge - 262 (March 25th 2024)
Task #1: Max Positive Negative
You are given an array of integers, @ints. Write a script to return the maximum number of either positive or negative integers in the given array.
Assumption there are no zero values (or we count them as neither +ve or -ve
Example 1
Input: -3,1,2,-1,3,-2,4 Output: 4
4 positive and 3 negative values – so answer is 4.
Example 2
Input: -1,-2,-3,1 Output: 3
3 negative values, 1 positive – answer 3
Example 3
Input: 1,2 Output: 2
Only 2 positive values – answer 2
Solution
We use the spaceship operator <=> to get the signum of each value – and the perl trick that in an array of 3 elements the -1 element is the 2 element.
We then use the spaceship operator again to get the maximum of the +/- counts – which are 1 & 2.
ADDENDUM
If you want to count 0s as both +ve and -ve then the last line can be replaced with “$c[ $c[1] <=> $c[2] ] + $c[0]“.
262-task1.pl - perl
sub max_positive_negative {
my @c = (0, 0, 0);
$c[ $_ <=> 0 ] ++ for @_;
$c[ $c[1] <=> $c[2] ]
}
Task #2: Count equal divisible
You are given an array of integers, @ints and an integer $k. Write a script to return the number of pairs ($i, $j) where $i < $j, $ints[$i] == $ints[$j] and $i*$j is divisible by $k;
Here we are going to produce two solutions, in both cases $k is passed in as the last element of the array (hence pop rather than shift):
Example 1
Input: @ints = (3,1,2,2,2,1,3), $k = 2 Output: 4
The two 3s are in positions 0 & 6 product even so + 1
The two 1s are in positions 1 & 5 the product is not even so + 0
The three 2s are in positions 2,3,4 all products are even so + 3
Example 2
Input: @ints = (1,2,3), $k = 1 Output: 0
None are equal
Example 3
Input: @ints = (2,1,1,1,1,3,3,3,3), $k = 12 Output: 2
Only index pairs to consider are 2,6; 3,4; 3,8; 4,6
Example 4
Input: @ints = (5,3,1,3,4,1,1,3,5,2,4,2,4,1,1,2,2,3,3,2),
$k = 6
Output: 13
Example 5
Input: @ints = (6,6,1,9,1,3,6,2,5,1,4,8,9,6,9,9,4,2,2,4,9,
6,2,4,8,4,1,6,9,4,4,6,4,7,3,4,4,4,1,4,6,6,
1,1,5,6,9,5,8,7,2,6,6,3,8,4,8,4,6,8,5,2,4,
8,5,5,3,3,6,7,4,8,6,5,5,7,3,9,4,4,4,4,7,2,
6,8,7,7,3,3,5,3,2,5,5,6,1,5,1,1),
$k = 12
Output: 171
Solution 1 - nested loop over all pairs (naive)
We loop through $i & $j – we check that the product is divisible by $k (it is divisible if ($i*$j) % $k is 0), then values are the same and if they increment the count $c – we use || and && to replace if not true and if true; Note as we are using a postfix for then “$j” is replaced by “$_“
perl
sub count_equal_divisible {
my($k,$c) = (pop,0);
for my $i ( 0 .. $#_ - 1 ) {
( $i * $_ ) % $k || $_[ $i ] == $_[ $_ ]
&& $c++ for $i + 1 .. $#_;
}
$c
}
Solution 2 - hashing and then looping over common values
In this case we create a hash for which the keys are the values in the list and the values are arrays of the indices of that number.
We then do the solution 1 loop for each element of the hash, i.e. the indices which have the same values – this though is simplified as we no longer need to do the value comparison inside the loops.
perl
sub count_equal_divisible_h {
my ( $k, $p, $c, %h ) = ( pop, 0, 0 );
push @{ $h{$_} }, $p++ for @_;
for my $x ( values %h ) {
while( @{$x} ) {
my $i = shift @{$x};
( $i * $_ ) % $k || $c++ for @{$x};
}
}
$c
}
~
Performance
For the examples in the challenge the speed for the naïve version is only roughly 2% faster than the hash method, so the hashing overhead is not great;
But an example with a list of 20 numbers between 1 & 5 the hash method is about 110% faster;
An example with a list of 100 numbers between 1 & 9 the hash method is about 420% faster;
About The Weekly Challenge
The weekly challenge was set up Mohammad Anwar approximately 5 years ago - each Monday two problems are set for the "team" to solve.
These are posted at: