DDSA Solutions

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

MediumView on LeetCode
ArrayHash TableSorting
Time: O(n log max)
Space: O(n)

Problem Overview

Find two numbers whose digit sums are equal and their sum is maximum.

Intuition

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

Algorithm

  1. 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
C#
// 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?

Related Problems