2473. Max Sum Of A Pair With Equal Sum Of Digits¶

Difficulty: Medium

2473. 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 <= 10⁵
1 <= nums[i] <= 10⁹

Solution¶

class Solution {
    public int maximumSum(int[] nums) {
        int n = nums.length;
        HashMap<Integer, MultiSet<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int current = nums[i], sum = 0;
            while (current > 0) {
                sum += current % 10;
                current /= 10;
            }
            if (!map.containsKey(sum)) map.put(sum, new MultiSet<>());
            map.get(sum).add(nums[i]);
        }
        int maxi = 0;
        for (Map.Entry<Integer, MultiSet<Integer>> x : map.entrySet()) {
            MultiSet<Integer> temp = x.getValue();
            if (temp.size <= 1) continue;
            int current_sum = temp.last();
            temp.remove(temp.last());
            current_sum += temp.last();
            maxi = Math.max(maxi, current_sum);
        } 
        if (maxi == 0) return -1;
        return maxi;
    }
    static class MultiSet<T> {
        TreeMap<T, Integer> frequency;
        TreeSet<T> set;
        int size;
        public MultiSet() {
            set = new TreeSet<>();
            frequency = new TreeMap<>();
            size = 0;
        }
        public void add(T elem) {
            if (frequency.get(elem) == null || frequency.get(elem) == 0) {
                frequency.put(elem, 0);
                set.add(elem);
            }
            frequency.put(elem, frequency.get(elem) + 1);
            size++;
        }
        public void remove(T elem) {
            if (!set.contains(elem)) return;
            frequency.put(elem, frequency.get(elem) - 1);
            if (frequency.get(elem) == 0) {
                set.remove(elem);
                frequency.remove(elem);
            }
            size--;
        }
        public T last() { return set.last(); }
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here