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.

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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: