Merge pull request #9178 from jo-37/contrib

Solution to task 2 in O(N)

2 files changed, 19 insertions, 3 deletions

diff --git a/challenge-245/jo-37/blog/Blog.md b/challenge-245/jo-37/blog/Blog.md
index 584d250c3d..7fc77126a7 100644
--- a/challenge-245/jo-37/blog/Blog.md
+++ b/challenge-245/jo-37/blog/Blog.md
@@ -75,10 +75,14 @@ Suppose we have `p = sum(d[i]) mod 3`.
 If the remaining set of digits is not empty, the largest number is formed from the digits in descending order.
 Otherwise there is no solution.
 
+It turns out, that sorting the digits using a standard algorithm would
+be the most expensive operation in this approach.  Thus using a specific
+O(N) sort for a collection of decimal digits.
+
 This results in the following implementation:
 ```
 sub largest_of_three {
-	my (@digits, @ind, $mod) = sort @_;
+    my (@digits, @ind, $mod) = dsort(@_);
     for (0 .. $#digits) {
         # The digit modulo 3
         my $digit = $digits[$_] % 3;
@@ -99,4 +103,10 @@ sub largest_of_three {
     @digits ? 0 + join '', reverse grep defined, @digits : -1;
 }
 
-```
\ No newline at end of file
+sub dsort {
+    my @digits;
+    $digits[$_]++ for @_;
+    map +($_) x ($digits[$_] // 0), 0 .. 9;
+}
+
+```
diff --git a/challenge-245/jo-37/perl/ch-2.pl b/challenge-245/jo-37/perl/ch-2.pl
index ef90057f91..a698a9f578 100755
--- a/challenge-245/jo-37/perl/ch-2.pl
+++ b/challenge-245/jo-37/perl/ch-2.pl
@@ -30,7 +30,7 @@ say largest_of_three(@ARGV);
 ### Implementation
 
 sub largest_of_three {
-	my (@digits, @ind, $mod) = sort @_;
+	my (@digits, @ind, $mod) = dsort(@_);
     for (0 .. $#digits) {
         # The digit modulo 3
         my $digit = $digits[$_] % 3;
@@ -51,6 +51,12 @@ sub largest_of_three {
     @digits ? 0 + join '', reverse grep defined, @digits : -1;
 }
 
+sub dsort {
+    my @digits;
+    $digits[$_]++ for @_;
+    map +($_) x ($digits[$_] // 0), 0 .. 9;
+}
+
 
 ### Examples and tests