Task — Largest of three

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.

Examples

Example 1
Input: @digits = (8, 1, 9)
Output: 981

981 % 3 == 0

Example 2
Input: @digits = (8, 6, 7, 1, 0)
Output: 8760

Example 3
Input: @digits = (1)
Output: -1

Analysis

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.

Try it 

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

Output

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