ETOOBUSY 🚀 minimal blogging for the impatient
PWC191 - Twice Largest
TL;DR
Here we are with TASK #1 from The Weekly Challenge #191. Enjoy!
The challenge
You are given list of integers,
@list
.Write a script to find out whether the largest item in the list is at least twice as large as each of the other items.
Example 1
Input: @list = (1,2,3,4) Output: -1 The largest in the given list is 4. However 4 is not greater than twice of every remaining elements. 1 x 2 <= 4 2 x 2 <= 4 2 x 3 > 4
Example 2
Input: @list = (1,2,0,5) Output: 1 The largest in the given list is 5. Also 5 is greater than twice of every remaining elements. 1 x 2 <= 5 2 x 2 <= 5 0 x 2 <= 5
Example 3
Input: @list = (2,6,3,1) Output: 1 The largest in the given list is 6. Also 6 is greater than twice of every remaining elements. 2 x 2 <= 6 3 x 2 <= 6 1 x 2 <= 6
Example 4
Input: @list = (4,5,2,3) Output: -1 The largest in the given list is 5. Also 5 is not greater than twice of every remaining elements. 4 x 2 > 5 2 x 2 <= 5 3 x 2 > 5
The questions
I guess we’re gradually transitioning towards TDC - Test Driven Challenges. This is not bad per-se, we would just need a few more examples.
So…
- What should we return? Assuming
-1
for false and1
for true. - What should we return if we are provided an empty list? This is tough,
I’ll just assume that
-1
is good. - What should we return if we only have one single entry in the list?
This time… I’ll assume that
1
is good. - What should we do with repeated value? I’ll assume that they can be ignored.
OK, let’s move on to…
The solution
The most efficient algorithm would need to look at least at all elements and actually needs looking at each of them at most once. So we have a good linear complexity, by doing this (assuming enough stuff in the array):
# initialize from the first two elements
my ($v1, $v2) = @list[0] < @list[1] ? @list[1,0] : @list[0,1];
# sweep the rest of the list
my $i = 1;
while (++$i < @list) {
($v1, $v2) = (@list[$i], $v1) if @list[$i] > $v1;
}
# now we can check if $v1 >= 2 * $v2
I hope that the code above is valid in both Raku and Perl (even though it’s going to raise a few warnings with the latter).
Anyway.
On the other hand… the fastest (programmer-wise, mind you!) solution can involve sorting the array in reverse order, and take the maximum value (ending up in first position) and the second-to-maximum value (ending up in second position) and compare them. Which is what we do in Raku here:
#!/usr/bin/env raku
use v6;
sub MAIN (*@list) { put twice-largest(@list) }
sub twice-largest (@list) {
my ($top, $next) = @list.sort({ $^a <=> $^b }).reverse.flat;
return -1 unless defined $top;
return 1 unless defined $next;
return ($top >= 2 * $next) ?? 1 !! -1;
}
With a little twist, in our Perl translation we’ll move the checks before doing the sorting, but for anything less it’s just the same algorithm as above:
#!/usr/bin/env perl
use v5.24;
use warnings;
use experimental 'signatures';
no warnings 'experimental::signatures';
say twice_largest(@ARGV);
sub twice_largest (@list) {
return -1 unless @list > 0;
return 1 unless @list > 1;
my ($top, $next) = reverse sort { $a <=> $b } @list;
return ($top >= 2 * $next) ? 1 : -1;
}
Well, nothing more to add I daresay… stay safe!