#2342

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Max Sum of a Pair With Equal Sum of Digits

Find the maximum sum of two numbers with equal digit sums in a given array of positive integers.

array hash table sorting heap priority queue

Problem Statement

You are given a 0-indexed array of positive integers called nums. You need to select two indices, i and j (where i != j), such that the sum of digits of nums[i] is equal to that of nums[j].

Your task is to find the maximum sum of nums[i] + nums[j] for all valid pairs i, j. If no such pair exists, return -1.

Examples

Example 1

Input: nums = [18,43,36,13,7]

Output: 54

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

There are no two numbers that satisfy the conditions, so we return -1.

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 109

Solution Approach

Array Scanning and Hash Lookup

We can efficiently solve this problem by scanning the array and storing the maximum value for each sum of digits in a hash table. This way, we can compare the current number's sum of digits with previously encountered sums to maximize the result.

Sum of Digits Calculation

For each number, calculate the sum of its digits. This can be done in constant time for each number, as the number of digits in the maximum possible value is small. We then use this sum to look up or update the hash table.

Maximizing the Sum

While scanning the array, we maintain the maximum sum of two numbers that share the same sum of digits. The hash table ensures that we can check for valid pairs efficiently.

Complexity Analysis

Metric	Value
Time	O(n \log m)
Space	O(\log m)

The time complexity is O(n log m), where n is the length of the array and m is the maximum number value (since calculating the sum of digits involves log m operations). The space complexity is O(log m) for the storage of sums of digits in the hash table.

What Interviewers Usually Probe

Candidate understands the importance of efficient hashing.
Candidate is familiar with digit manipulation and sum of digits calculation.
Candidate recognizes the challenge of balancing time complexity with correctness.

Common Pitfalls or Variants

Common pitfalls

Not efficiently updating the hash table, leading to unnecessary re-checks.
Overlooking edge cases where no valid pairs exist, returning the correct -1 value.
Misunderstanding the sum of digits calculation and applying it incorrectly.

Follow-up variants

What happens if the array only has one number?
How does the solution handle very large numbers or arrays at the upper constraint limits?
Can we optimize this further if there are only a few numbers with unique digit sums?

FAQ

What is the time complexity of solving Max Sum of a Pair With Equal Sum of Digits?

The time complexity is O(n log m), where n is the array length and m is the value of the largest number in the array.

How do I calculate the sum of digits for large numbers in this problem?

You can calculate the sum of digits by repeatedly dividing the number by 10 and adding the remainders. This process takes O(log m) time, where m is the number itself.

How can I handle cases where no valid pair exists?

If no valid pair exists, the correct output is -1. Ensure your algorithm correctly handles this case by checking the hash table for valid pairs.

What is the best approach for handling large arrays in Max Sum of a Pair With Equal Sum of Digits?

Efficient array scanning combined with hash lookups ensures that the algorithm runs in linear time with respect to the array length, making it scalable for large inputs.

What is the pattern used in Max Sum of a Pair With Equal Sum of Digits?

The pattern involves array scanning combined with hash table lookup to track the maximum sum of numbers that share the same sum of digits.

terminal

Solution

Solution 1: Hash Table

We can use a hash table $d$ to record the maximum value corresponding to each digit sum, and initialize an answer variable $ans = -1$.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        d = defaultdict(int)
        ans = -1
        for v in nums:
            x, y = 0, v
            while y:
                x += y % 10
                y //= 10
            if x in d:
                ans = max(ans, d[x] + v)
            d[x] = max(d[x], v)
        return ans

Continue Practicing

#2357 make array zero by subtracting equal amounts #2402 meeting rooms iii #2456 most popular video creator