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 and 1 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 < @list ? @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!

Comments? Octodon, , GitHub, Reddit, or drop me a line!