Plus versus minus

Weekly challenge 262 — 25 March 2024

Week 262 - 25 Mar 2024

Task 2

You are given an array of integers, @ints and an integer $k. Write a script to return the number of pairs (i, j) where:

- 0 <= i < j < size of @ints
- ints[i] == ints[j]
- i x j is divisible by k

Example 1Input: @ints = (3,1,2,2,2,1,3) and $k = 2 Output: 4 (0, 6) => ints[0] == ints[6] and 0 x 6 is divisible by 2 (2, 3) => ints[2] == ints[3] and 2 x 3 is divisible by 2 (2, 4) => ints[2] == ints[4] and 2 x 4 is divisible by 2 (3, 4) => ints[3] == ints[4] and 3 x 4 is divisible by 2Example 2Input: @ints = (1,2,3) and $k = 1 Output: 0

There seems little advantage to doing anything other than coding the task more-or-less as stated, which is to say using two nested loops over i and j and eliminating the pairs which don't satisfy conditions b and c in the task statement. So that's what I did.

It's notable that since 0 is a multiple of anything, `$ints[0]`

and any subsequent
member with the same value will qualify, regardless of `$k`

. For example, if `$ints[0] == 13`

and `$ints[99] == 13`

, this will qualify since 0 * 99 is a multiple of 13 - or of anything else.

#!/usr/bin/perl # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge use v5.26; # The Weekly Challenge - 2024-03-25 use utf8; # Week 262 - task 2 - Count equal divisible use warnings; # Peter Campbell Smith binmode STDOUT, ':utf8'; my (@ints, $j); count_equal_divisible([3, 1, 2, 2, 2, 1, 3], 2); count_equal_divisible([1, 2, 3], 1); # bigger example for $j (0 .. 99) { push @ints, int(rand(50) + 1); } count_equal_divisible(\@ints, 23); sub count_equal_divisible { my (@ints, $i, $j, $ij, $k, $count, $explain); # initialise @ints = @{$_[0]}; $k = $_[1]; $count = 0; $explain = ''; # loop over all pairs where $j > $i for $i (0 .. @ints - 2) { for $j ($i + 1 .. @ints - 1) { # discard unless values are equal next unless $ints[$i] == $ints[$j]; # discard unless $i * $j is a multiple of $k $ij = $i * $j; next unless $ij / $k == int($ij / $k); # found an answer $count ++; $explain .= qq[$i * $j = $ij, ]; } } # show results say qq[\nInput: \@ints = (] . join(', ', @ints) . qq[), \$k = $k]; $explain =~ s|(.*)..$|($1)|; say qq[Output: $count $explain]; }

Input: @ints = (3, 1, 2, 2, 2, 1, 3), $k = 2 Output: 4 (0 * 6 = 0, 2 * 3 = 6, 2 * 4 = 8, 3 * 4 = 12) Input: @ints = (1, 2, 3), $k = 1 Output: 0 Input: @ints = (50, 40, 43, 38, 34, 20, 19, 17, 13, 28, 26, 31, 35, 39, 33, 41, 28, 46, 43, 13, 22, 2, 11, 30, 35, 26, 34, 24, 8, 2, 44, 50, 38, 33, 46, 15, 23, 43, 2, 35, 49, 33, 50, 24, 25, 33, 22, 12, 7, 38, 50, 28, 34, 13, 18, 36, 12, 49, 37, 3, 47, 42, 22, 19, 41, 17, 43, 47, 10, 10, 43, 7, 13, 32, 47, 35, 38, 40, 44, 44, 32, 5, 12, 19, 34, 29, 19, 5, 30, 11, 12, 41, 19, 28, 8, 33, 19, 32, 50, 27), $k = 23 Output: 13 (0 * 31 = 0, 0 * 42 = 0, 0 * 50 = 0, 0 * 98 = 0, 6 * 92 = 552, 20 * 46 = 920, 23 * 88 = 2024, 46 * 62 = 2852, 63 * 92 = 5796, 68 * 69 = 4692, 83 * 92 = 7636, 86 * 92 = 7912, 92 * 96 = 8832)

Peter Campbell Smith is hereby placed in the public domain