Skip to content

← leetcode

Max Sum of a Pair With Equal Sum of Digits

· Medium

LeetCode problem 2342

You can just use a hashmap, mp, to keep track of the maximum integer for each digit sum, index. However, since we know there is a maximum number of digit sums (81 since 1 <= nums[i] <= 10^9, meaning largest digit sum is 9 * 9 = 81) we can just use an array of constant size instead of an unordered_map.

Then:

  • if the indexed digit sum is empty, we can just assign the current digit
  • else, we can update ans if the sum between the current digit and the indexed digit sum is larger (ans = max(ans, mp[index]) and also update mp[index] if the current digit is larger

code

class Solution {
public:
    int maximumSum(vector<int>& nums) {
        int mp[82];
        memset(mp, -1, sizeof(int)*82);
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            int index = 0;
            int val = nums[i];
            while(nums[i] > 0) {
                index += nums[i]%10;
                nums[i] /= 10;
            }
            if (mp[index] == -1) {
                mp[index] = val;
            } else {
                ans = max(ans, mp[index] + val);
                mp[index] = max(val, mp[index]);
            }
        }
        return ans == 0 ? -1 : ans;
    }
};

complexity

  • Time: O(n log m) where m is the largest number
  • Space: O(1)