## 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.

Advertisement

Pages: 1 2

### 4 Responses to “2Max”

1. Zack said

Interesting exercise. Here is my take on it using Julia 1.4: https://pastebin.com/uEPBeKBc

Have a nice weekend!

2. matthew said

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 max
```
3. Daniel said

Here’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:

```93
-1
```
4. Globules said

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]
]
```
```\$ ./max2
-1
-1
93
93
2293
```