Problem #1102: max

An interesting problem that can be solved with a linear scan and storing just the two max numbers. Code below, cheers, ACC.

Max Sum of a Pair With Equal Sum of Digits - LeetCode

2342. Max Sum of a Pair With Equal Sum of Digits

Medium

You are given a 0-indexed array nums consisting of positive integers. You can choose two indices i and j, such that i != j, and the sum of digits of the number nums[i] is equal to that of nums[j].

Return the maximum value of nums[i] + nums[j] that you can obtain over all possible indices i and j that satisfy the conditions.

 

Example 1:

Input: nums = [18,43,36,13,7]
Output: 54
Explanation: The pairs (i, j) that satisfy the conditions are:
- (0, 2), both numbers have a sum of digits equal to 9, and their sum is 18 + 36 = 54.
- (1, 4), both numbers have a sum of digits equal to 7, and their sum is 43 + 7 = 50.
So the maximum sum that we can obtain is 54.

Example 2:

Input: nums = [10,12,19,14]
Output: -1
Explanation: There are no two numbers that satisfy the conditions, so we return -1.

 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

Accepted

11,159

Submissions

22,466

public class Solution {
    public int MaximumSum(int[] nums)
    {
        Hashtable mapSumDigitsToMax = new Hashtable();

        int retVal = -1;
        foreach (int n in nums)
        {
            int sumDigits = SumOfDigits(n);

            if (!mapSumDigitsToMax.ContainsKey(sumDigits)) mapSumDigitsToMax.Add(sumDigits, new int[] { 0, 0 });

            int[] max = (int[])mapSumDigitsToMax[sumDigits];
            if (n >= max[0])
            {
                max[1] = max[0];
                max[0] = n;
            }
            else if (n > max[1])
            {
                max[1] = n;
            }

            if (max[0] > 0 && max[1] > 0)
            {
                retVal = Math.Max(retVal, max[0] + max[1]);
            }
        }

        return retVal;
    }

    private int SumOfDigits(int n)
    {
        int retVal = 0;
        while (n > 0)
        {
            retVal += (n % 10);
            n /= 10;
        }

        return retVal;
    }
}