I’ve been doing the Weekly
Challenges. The
latest
involved more list searching and a variation on the greatest common
divisor. (Note that this is open until 30 October 2022.)
Task 1: Divisible Pairs
You are given list of integers @list of size $n
and divisor $k
.
Write a script to find out count of pairs in the given list that
satisfies the following rules.
The pair (i, j) is eligible if and only if
a) 0 <= i < j < len(list)
b) list[i] + list[j] is divisible by k
This has a strong resemblance to 187 task 2, and I used my code from
that as the basis for this one: some languages have a combinations
generator readily available, others don't and get simple nested loops
since I don't have to work to an arbitrary depth.
Lua:
function divisiblepairs(a, k)
local ct = 0
for ai = 1,#a-1 do
for bi = ai+1,#a do
if (a[ai] + a[bi]) % k == 0 then
ct = ct + 1
end
end
end
return ct
end
Or, with a combination generator, Ruby:
def divisiblepairs(a, k)
ct = 0
a.combination(2) do |b|
if (b[0] + b[1]) % k == 0 then
ct += 1
end
end
return ct
end
Task 2: Total Zero
You are given two positive integers $x
and $y
.
Write a script to find out the number of operations needed to make both ZERO. Each operation is made up either of the followings:
$x = $x - $y if $x >= $y
or
$y = $y - $x if $y >= $x (using the original value of $x)
This is of course Euclid's algorithm for greatest common divisor,
except that we're counting the steps rather than the final result. One
could get clever with modulus operations to do multiple steps at once
(a variant of the Euclidean algorithm), but it seemed to me that the
simplest approach to write and debug was just to do one subtraction at
a time.
The end cases in my implementation are:
a == b == 0
– we won't reach this so it's special-cased at the
start.
a == b
– one more step gets us to a == b == 0
, and everything
else terminates here. (So I don't have to worry about temporary
variables to do the final double subtraction.)
a ≠ b
– subtract smaller from larger, increment count and
continue.
In Raku:
sub totalzero($aa, $bb) {
The special case for zero steps:
if ($aa == 0 && $bb == 0) {
return 0;
}
Otherwise, set the count to 1.
my $a = $aa;
my $b = $bb;
my $ct = 1;
while (True) {
Each time the values aren't equal, increment the count and continue.
if ($a == $b) {
return $ct;
}
$ct++;
if ($a > $b) {
$a -= $b;
} else {
$b -= $a;
}
}
}
Full code on
github.
Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.