2Max
June 5, 2020
Today’s exercise comes from Stack Overflow:
Given an array A consisting of N integers, return the maximum sum of two numbers whose digits add up to an equal sum. If there are not two numbers whose digits have an equal sum, the function should return -1. For example, A = [51, 71, 17, 42] would output 93 because there are two sets of numbers with the same digit-sum, (51, 42) with a digit-sum of 6 and (17, 71) with a digit-sum of 8, and the first pair has the maximum sum of two numbers of 93.
Your task is to write a program to calculated the requested maximum sum. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
Interesting exercise. Here is my take on it using Julia 1.4: https://pastebin.com/uEPBeKBc
Have a nice weekend!
Scan the array, keeping track of the largest number seen so far for each digit sum:
def max2(a): s = {} # s[n] = largest k seen so far with dsum(k) = n max = -1 for n in a: dsum = sum(int(c) for c in str(n)) if dsum not in s: s[dsum] = n # A new digit sum else: m = s[dsum] if max < 0 or m+n > max: max = m+n # Update max if n > m: s[dsum] = n # Update s return maxHere’s a not-particularly efficient, not-particularly readable solution in Python.
def two_max(l): p = sorted(((sum(int(c) for c in str(x)), x) for x in l), reverse=True) return max((b + d for (a, b), (c, d) in zip(p, p[1:]) if a == c), default=-1) print(two_max([51, 71, 17, 42])) print(two_max([1, 2, 3, 4, 5, 6]))Output:
Here’s a Haskell version.
import Data.List (insertBy, unfoldr) import Data.Map (elems, fromListWith) import Data.Ord (Down(..), comparing) max2 :: Integral a => [a] -> a max2 xs = maximum ((-1) : top2Sums xs) top2Sums :: Integral a => [a] -> [a] top2Sums = map sum . filter ((==2) . length) . elems . fromListWith (\[n] -> top2 n) . digitSums top2 :: Ord a => a -> [a] -> [a] top2 x = take 2 . insertBy (comparing Down) x digitSums :: Integral a => [a] -> [(a, [a])] digitSums = map (\x -> (sum (digits x), [x])) digits :: Integral a => a -> [a] digits = unfoldr step where step 0 = Nothing step n = let (q, r) = quotRem n 10 in Just (r, q) main :: IO () main = mapM_ (print . max2) [ [] , [0] , [51, 71, 17, 42] , [51, 71, 17, 42, 2223] , [51, 71, 17, 42, 2222] ]