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

MediumView on LeetCode

Array Hash Table Sorting

Time: O(n log max)

Space: O(n)

Intuition

Find two numbers whose digit sums are equal and their sum is maximum. Group by digit sum, take top-2 per group.

Algorithm

1Map: digitSum -> max value seen. For each num: ds = digitSum(num). If ds in map: ans = max(ans, map[ds] + num). map[ds] = max(map[ds], num).

Common Pitfalls

•Only need the maximum value per digit sum group. Update max after using it.

2342.cs

// Approach: Group numbers by digit sum; for each group keep top 2 and sum them.
// Time: O(n log max) Space: O(n)

public class Solution
{
    public int MaximumSum(int[] nums)
    {
        const int kMax = 9 * 9;  // 999,999,999
        int ans = -1;
        List<List<int>> count = new List<List<int>>(new List<int>[kMax + 1]);

        for (int i = 0; i <= kMax; i++)
            count[i] = new List<int>();

        foreach (int num in nums)
            count[GetDigitSum(num)].Add(num);

        foreach (List<int> groupNums in count)
        {
            if (groupNums.Count < 2)
                continue;
            groupNums.Sort((a, b) => b.CompareTo(a));
            ans = Math.Max(ans, groupNums[0] + groupNums[1]);
        }

        return ans;
    }

    private int GetDigitSum(int num)
    {
        int digitSum = 0;
        while (num > 0)
        {
            digitSum += num % 10;
            num /= 10;
        }
        return digitSum;
    }
}

Was this solution helpful?