Peter
Peter Campbell Smith

Plus versus minus

Weekly challenge 262 — 25 March 2024

Week 262 - 25 Mar 2024

Task 2

Task — Count equal divisible

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

  1. 0 <= i < j < size of @ints
  2. ints[i] == ints[j]
  3. i x j is divisible by k

Examples


Example 1
Input: @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 2

Example 2
Input: @ints = (1,2,3) and $k = 1
Output: 0

Analysis

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.

Try it 

Try running the script with any input:



example: 1, 2, 3, 4, 5, 5, 4, 3, 2, 1



example: 3

Script


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

Output


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)

The content of this website which has been created by
Peter Campbell Smith is hereby placed in the public domain