Find the target and

merge the inventory

Weekly challenge 263 — 1 April 2024

Week 263 - 1 Apr 2024

Task 1

You are given an array of integers, @ints and a target element $k. Write a script to return the list of indices in the sorted array where the element is same as the given target element.

Example 1Input: @ints = (1, 5, 3, 2, 4, 2), $k = 2 Output: (1, 2) Sorted array: (1, 2, 2, 3, 4, 5) Target indices: (1, 2) as $ints[1] = 2 and $k[2] = 2Example 2Input: @ints = (1, 2, 4, 3, 5), $k = 6 Output: () No element in the given array matching the given target.Example 3Input: @ints = (5, 3, 2, 4, 2, 1), $k = 4 Output: (4) Sorted array: (1, 2, 2, 3, 4, 5) Target index: (4) as $ints[4] = 4

The obvious solution is to sort `@ints`

, and then there is a one-line answer:
`$output .=`

$ints[$_] == $k ? qq[$_, ] : '' for 0 .. @ints - 1;

- but that's not what I've submitted.

Instead, and because a sort is
expensive if `@ints`

is very large - say a million integers - a better
algorithm is to pass once through the __unsorted__ array:

- counting the number of integers less than
`$k`

- call that`$n`

, and - counting the number of instances of
`$k`

- call that`$m`

.

The solution is then simply `$n .. ($n + $m - 1)`

.

I tried that with a million integers and the answer came back in a few seconds.

#!/usr/bin/perl # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge use v5.26; # The Weekly Challenge - 2024-04-01 use utf8; # Week 263 - task 1 - Target index use warnings; # Peter Campbell Smith binmode STDOUT, ':utf8'; my (@ints, $j); target_index([1, 5, 3, 2, 4, 2], 2); target_index([1, 2, 4, 3, 5], 6); target_index([5, 3, 2, 4, 2, 1], 4); # bigger example for $j (0 .. 500) { push @ints, int(rand(30) + 1); } target_index(\@ints, 15); sub target_index { my (@ints, $int, $k, $m, $n, $output); # initialise @ints = @{$_[0]}; $k = $_[1]; say qq[\nInput: \@ints = (] . join(', ', @ints) . qq[), \$k = $k]; # count integers less than $k and equal to $k $n = $m = 0; for $int (@ints) { $n ++ if $int < $k; $m ++ if $int == $k; } # show results $output = ''; $output .= qq[$_, ] for $n .. ($n + $m - 1); say qq[Output: (] . substr($output, 0, -2) . ')'; }

Input: @ints = (1, 5, 3, 2, 4, 2), $k = 2 Output: (1, 2) Input: @ints = (1, 2, 4, 3, 5), $k = 6 Output: () Input: @ints = (5, 3, 2, 4, 2, 1), $k = 4 Output: (4) Input: @ints = (500 random numbers in 0 .. 29), $k = 15 Output: (252, 253, 254, 255, 256, 257, 258, 259, 260, 261, 262, 263, 264, 265)

Peter Campbell Smith is hereby placed in the public domain