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

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

Approach 01:

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    int maximumSum(vector<int>& numbers) {
        constexpr int maxDigitSum = 81; // Maximum possible digit sum (9*9)
        int maxPairSum = -1;
        vector<vector<int>> digitSumGroups(maxDigitSum + 1);

        for (const int number : numbers)
            digitSumGroups[calculateDigitSum(number)].push_back(number);

        for (vector<int>& group : digitSumGroups) {
            if (group.size() < 2)
                continue;
            ranges::sort(group, greater<>());
            maxPairSum = max(maxPairSum, group[0] + group[1]);
        }

        return maxPairSum;
    }

private:
    int calculateDigitSum(int number) {
        int digitSum = 0;
        while (number > 0) {
            digitSum += number % 10;
            number /= 10;
        }
        return digitSum;
    }
};

from collections import defaultdict

class Solution:
    def maximumSum(self, numbers):
        maxDigitSum = 81  # Maximum possible digit sum (9*9)
        maxPairSum = -1
        digitSumGroups = defaultdict(list)

        for number in numbers:
            digitSumGroups[self.calculateDigitSum(number)].append(number)

        for group in digitSumGroups.values():
            if len(group) < 2:
                continue
            group.sort(reverse=True)
            maxPairSum = max(maxPairSum, group[0] + group[1])

        return maxPairSum

    def calculateDigitSum(self, number):
        digitSum = 0
        while number > 0:
            digitSum += number % 10
            number //= 10
        return digitSum

Time Complexity:

• Calculating Digit Sums:

  For each number, computing the digit sum takes \( O(\log N) \), where \( N \) is the largest number in the array.

• Grouping Numbers:

  Each number is placed in one of at most 81 groups, taking \( O(N) \) time.

• Sorting Each Group:

  Sorting each group takes at most \( O(K \log K) \), where \( K \) is the number of elements in that group.

• Overall Time Complexity:

  \( O(N \log N) \), since the dominant factor is sorting the groups.

Space Complexity:

• Digit Sum Groups:

  Storing at most \( O(N) \) numbers in the groups results in \( O(N) \) space.

• Overall Space Complexity:

  \( O(N) \), as we store a categorized version of the input.