Popular languages and

largest threefold

Weekly challenge 245 — 27 November 2023

Week 245 - 27 Nov 2023

Task 2

You are given an array of integers >= 0. Write a script to return the largest number formed by concatenating some of the given integers in any order which is also multiple of 3. Return -1 if none found.

Example 1Input: @digits = (8, 1, 9) Output: 981 981 % 3 == 0Example 2Input: @digits = (8, 6, 7, 1, 0) Output: 8760Example 3Input: @digits = (1) Output: -1

The task definition seems unambiguous: we are provided with a set of integers >= 0.

However, the examples only show single digits, and they are provided in an array
called `@digits`

, so there is some question as to whether only single digit
integers is implied. However, I have assumed not.

Having settled that, there is now the question of whether we have to cope with a concatenation of all the supplied numbers being larger than a Perl integer. I have assumed that we have cater for that, but rather than going into BigInt territory I have come up with a solution that does not - essentially by treating the numbers as strings.

Clearly we will need a function that determines whether a number is a multiple
of 3. Fortunately, if the sum of the digits of any number is a
multiple of 3, then so is the original number. So we can treat a large number as
simply a string of digits, and add them together. That sum will not be a BigInt
so we can simply test `$sum % 3 == 0`

.

The next issue to tackle is that if the number of integers supplied is large, there could be a very large number of combinations to test. However, we can cut that down massively.

First, let's consider the combinations in decreasing number of numbers. So if there are 6 integers, we'll first test the concatenation of all 6, then all the possible combinations of 5 of them, and so on. For each combination, we'll first reverse-sort it and then concatenate all the members to form a large integer.

We test that to see if it is a multiple of three (see above)
and whether it's larger than the largest one we have already seen. But - just a moment -
this concatenated number might be a BigInt so we can't just use `>`

to check if it's larger.

Instead, firstly we need to check if it has fewer
digits than the best so far, in which case it definitely isn't larger,
or if it has more digits, in which case it definitely is the new best-so-far,
or if it has they have the same number of digits we need to use `gt`

to
compare them alphanumerically so see whether we have a new winner.

And now, importantly, if we have a result comprised of n of the input numbers concatenated, no concatenation of fewer than n numbers will be divisible by 3 and be larger than the one already found, so we can stop.

#!/usr/bin/perl use v5.26; # The Weekly Challenge - 2023-11-27 use utf8; # Week 245 task 2 - Largest of three use strict; # Peter Campbell Smith use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge use Algorithm::Combinatorics 'combinations'; my ($j, @digits); largest_of_three(8, 6, 7, 1, 0); largest_of_three(0); largest_of_three(18446744073709551614, 3); largest_of_three(333, 666, 1, 4, 7); largest_of_three(1, 4); for $j (0..9) { push @digits, int(rand(10000)); } largest_of_three(@digits); sub largest_of_three { my (@digits, $c, $iter, $comb, @set, $value, $result, $length); # loop over sizes of combination to consider @digits = @_; $result = -1; $length = 0; for ($c = @digits; $c > 0; $c --) { # iterate over combinations of length $c numbers $iter = combinations(\@digits, $c); while ($comb = $iter->next) { # reverse sort them alphabetically to get best bet first @set = reverse sort @$comb; # concatenate them and see if that's the best so far $value = join('', @set); # this if is just: if (mult_of_3($value) and $value > $result) accommodating BigInts if (is_mult_of_3($value) and (length($value) > $length or (length($value) eq $length and $value gt $result))) { $result = $value; $length = length($result); } } # if we have an answer, no smaller subset will produce a larger number last if $result >= 0; } say qq[\nInput: \@digits = (] . join(q[, ], @_) . q[)]; say qq[Output: $result]; } sub is_mult_of_3 { my ($input, $sum); $input = shift; $sum = 0; $sum += $1 while $input =~ m|(\d)|g; return $sum % 3 == 0; }

Input: @digits = (8, 6, 7, 1, 0) Output: 8760 Input: @digits = (0) Output: 0 Input: @digits = (18446744073709551614, 3) Output: 3 Input: @digits = (333, 666, 1, 4, 7) Output: 766643331 Input: @digits = (1, 4) Output: -1 Input: @digits = (2819, 9342, 5993, 3896, 2319, 2403, 5254, 3584, 9110, 5144) Output: 934291105993514438963584281924032319

Peter Campbell Smith is hereby placed in the public domain