Divisible pairs and

reduce to nothing

Weekly challenge 188 — 24 October 2022

Week 188 - 24 Oct 2022

Task 1

You are given list of integers `@list`

of size `$n`

and a 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

- 0 <= i < j < len(list)
- list[i] + list[j] is divisible by k

Example 1Input: @list = (4, 5, 1, 6), $k = 2 Output: 2Example 2Input: @list = (1, 2, 3, 4), $k = 2 Output: 2Example 3Input: @list = (1, 3, 4, 5), $k = 3 Output: 2Example 4Input: @list = (5, 1, 2, 3), $k = 4 Output: 2Example 5Input: @list = (7, 2, 4, 5), $k = 4 Output: 1

The way I did this is to generate all the pairs and check their divisibility by the given divisor. All the examples given include only unique positive integers. The task is not significantly different if zero and negative integers are included, but if the same integer appears more than once (eg list = 1, 2, 3, 3, divisor = 4) do we count distinct pairings (1 and the first 3, 1 and the second 3) or merely distinct pairs (just 1 and 3)? I guessed yes.

#!/usr/bin/perl # Peter Campbell Smith - 2022-10-26 # PWC 188 task 1 use v5.28; use utf8; use warnings; binmode(STDOUT, ':utf8'); my (@tests, @list, $k, $n, $i, $j, $count, $reason); # test input (\@list, $k ...) @tests = ([4, 5, 1, 6], 2, [1, 2, 3, 4], 2, [1, 3, 4, 5], 3, [5, 1, 2, 3], 4, [7, 2, 4, 5], 4, [3, 6, 9, 12, 15], 11, [7, 9, 8, 3, 4, 0, 1, 11, 6, 12, 10, 6, 2], 3); # loop over tests while ($tests[0]) { # initialise @list = @{shift @tests}; $k = shift @tests; $n = scalar @list; $count = 0; $reason = ''; #loop over i and j such as to apply test a for $i (0 .. $n - 2) { for $j ($i + 1 .. $n - 1) { # apply test b next unless (($list[$i] + $list[$j]) % $k) == 0; # found an answer $count ++; $reason .= qq[($list[$i] + $list[$j]), ]; } } # output say qq[\nInput: \@list = ] . join(', ', @list) . qq[, \$k = $k\nOutput: $count\nReason: ] . substr($reason, 0, -2); }

Input: @list = 4, 5, 1, 6, $k = 2 Output: 2 Reason: (4 + 6), (5 + 1) Input: @list = 1, 2, 3, 4, $k = 2 Output: 2 Reason: (1 + 3), (2 + 4) Input: @list = 1, 3, 4, 5, $k = 3 Output: 2 Reason: (1 + 5), (4 + 5) Input: @list = 5, 1, 2, 3, $k = 4 Output: 2 Reason: (5 + 3), (1 + 3) Input: @list = 7, 2, 4, 5, $k = 4 Output: 1 Reason: (7 + 5) Input: @list = 3, 6, 9, 12, 15, $k = 11 Output: 0 Reason: Input: @list = 7, 9, 8, 3, 4, 0, 1, 11, 6, 12, 10, 6, 2, $k = 3 Output: 27 Reason: (7 + 8), (7 + 11), (7 + 2), (9 + 3), (9 + 0), (9 + 6), (9 + 12), (9 + 6), (8 + 4), (8 + 1), (8 + 10), (3 + 0), (3 + 6), (3 + 12), (3 + 6), (4 + 11), (4 + 2), (0 + 6), (0 + 12), (0 + 6), (1 + 11), (1 + 2), (11 + 10), (6 + 12), (6 + 6), (12 + 6), (10 + 2)

The content of this website which has been created by

Peter Campbell Smith is hereby placed in the public domain

Peter Campbell Smith is hereby placed in the public domain