Peter
Peter Campbell Smith

Divisible pairs and
reduce to nothing

Weekly challenge 188 — 24 October 2022

Week 188 - 24 Oct 2022

Task 1

Task — Divisible Pairs

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

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

Examples


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

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

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

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

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

Analysis

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.

Try it 

Try running the script with any input:



example: 4, 5, 1, 6



example: 2

Script


#!/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); 
}

Output


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