RogerBW's Blog

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.