2Max

June 5, 2020

One way to solve this problem is to collect input numbers with similar digit-sums in a hash table, compute the two-maximums of each hash set, and return the maximum. Instead, we solve the problem using the cluster function of a previous exercise and a few auxiliary functions:

(define (2max xs)
  (if ( xs))))
(define (sum-digits n)
  (sum (digits n)))
(define (f x)
  (apply max (map sum (map 2max
    (cluster sum-digits <lt; xs)))))

Here are two examples:

> (f '(51 17 71 42))
93
> (f '(1 2 3 4 5 6))
-1

The pieces are individually small and easy to understand, which makes the whole function equally easy to understand. You can run the program at https://ideone.com/KcT9Ix.

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: