Problem Description

You have an array nums containing positive integers, and you need to find two different elements whose digit sums are equal, then return their maximum possible sum.

Here's what you need to do:

• Pick two different indices i and j (where i != j)
• Calculate the sum of digits for nums[i] and nums[j]
• If these digit sums are equal, consider the sum nums[i] + nums[j]
• Return the maximum such sum across all valid pairs

The digit sum means adding up all individual digits of a number. For example:

• The digit sum of 243 is 2 + 4 + 3 = 9
• The digit sum of 81 is 8 + 1 = 9

If you can't find any two numbers with equal digit sums, return -1.

Example scenarios:

• If nums = [18, 43, 36, 13, 7]:
  • 18 has digit sum 1 + 8 = 9
  • 36 has digit sum 3 + 6 = 9
  • These two numbers have equal digit sums, so we can pair them: 18 + 36 = 54
  • 43 has digit sum 4 + 3 = 7
  • 7 has digit sum 7
  • These also match, giving us: 43 + 7 = 50
  • The maximum is 54

The goal is to find the largest possible sum among all valid pairs with matching digit sums.

Intuition

When looking for pairs with equal digit sums, we need to group numbers by their digit sum. The key insight is that we don't need to track all numbers with the same digit sum - we only need to track the maximum value for each digit sum group.

Why? Because to maximize nums[i] + nums[j] where both have the same digit sum, we want the two largest numbers from that group.

Think of it this way: if we have three numbers [18, 36, 45] all with digit sum 9, the maximum pair sum would be 36 + 45 = 81. We don't need to consider 18 once we've seen larger numbers with the same digit sum.

This leads to a greedy strategy:

1. As we traverse the array, we calculate each number's digit sum
2. For each digit sum, we maintain only the largest number we've seen so far
3. When we encounter a new number with a digit sum we've seen before, we can immediately calculate a potential answer by adding it to the previously stored maximum
4. Then we update our stored maximum if the current number is larger

This single-pass approach works because:

• When we see the second number with a particular digit sum, we form a pair with the first (which is the only one available)
• When we see the third or later numbers with that digit sum, we always pair with the largest previous one
• We keep updating the stored maximum to ensure future numbers can pair with the best possible partner

The beauty of this approach is its efficiency - we only need O(n) time and minimal space (at most 81 different digit sums for numbers up to 10^9).

Learn more about Sorting and Heap (Priority Queue) patterns.

Solution Approach

We implement the solution using a hash table to track the maximum value for each digit sum:

1. Initialize data structures:

   • Create a hash table d (using defaultdict(int)) to store the maximum number for each digit sum
   • Set ans = -1 to track the maximum pair sum (returns -1 if no valid pair exists)

2. Process each number in the array: For each number v in nums:

   a. Calculate the digit sum:

   x, y = 0, v
   while y:
       x += y % 10
       y //= 10

   • x accumulates the digit sum
   • y % 10 extracts the last digit
   • y //= 10 removes the last digit
   • Continue until all digits are processed

   b. Check for a valid pair:

   • If digit sum x already exists in hash table d, we found a pair!
   • Calculate the pair sum: d[x] + v
   • Update the answer: ans = max(ans, d[x] + v)

   c. Update the hash table:

   • Store or update the maximum value for this digit sum: d[x] = max(d[x], v)
   • This ensures future numbers with the same digit sum can pair with the best possible partner

3. Return the result:

   • Return ans, which contains the maximum pair sum or -1 if no valid pair was found

Time Complexity: O(n × log M) where n is the array length and M is the maximum value in the array (for digit sum calculation)

Space Complexity: O(k) where k is the number of unique digit sums (at most 81 for numbers up to 10^9)

Optimization Note: Since the maximum possible digit sum is 81 (nine 9's), we could replace the hash table with a fixed-size array of length 100 for slightly better performance.

Example Walkthrough

Let's trace through the solution with nums = [18, 43, 36, 13, 7]:

Initial state:

• Hash table d = {} (empty)
• Answer ans = -1

Step 1: Process 18

• Calculate digit sum: 1 + 8 = 9
• Check if digit sum 9 exists in d: No
• Update d[9] = 18
• Current state: d = {9: 18}, ans = -1

Step 2: Process 43

• Calculate digit sum: 4 + 3 = 7
• Check if digit sum 7 exists in d: No
• Update d[7] = 43
• Current state: d = {9: 18, 7: 43}, ans = -1

Step 3: Process 36

• Calculate digit sum: 3 + 6 = 9
• Check if digit sum 9 exists in d: Yes! d[9] = 18
• Calculate pair sum: 18 + 36 = 54
• Update answer: ans = max(-1, 54) = 54
• Update d[9] = max(18, 36) = 36
• Current state: d = {9: 36, 7: 43}, ans = 54

Step 4: Process 13

• Calculate digit sum: 1 + 3 = 4
• Check if digit sum 4 exists in d: No
• Update d[4] = 13
• Current state: d = {9: 36, 7: 43, 4: 13}, ans = 54

Step 5: Process 7

• Calculate digit sum: 7
• Check if digit sum 7 exists in d: Yes! d[7] = 43
• Calculate pair sum: 43 + 7 = 50
• Update answer: ans = max(54, 50) = 54
• Update d[7] = max(43, 7) = 43
• Current state: d = {9: 36, 7: 43, 4: 13}, ans = 54

Final Result: 54

The algorithm found two valid pairs:

• Numbers with digit sum 9: (18, 36) with sum 54
• Numbers with digit sum 7: (43, 7) with sum 50

The maximum pair sum is 54, which comes from pairing 18 and 36.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log M)

The algorithm iterates through each element in the array once, which takes O(n) time. For each element v, it calculates the sum of digits by repeatedly dividing by 10 and extracting the remainder. The number of iterations in this digit extraction process is proportional to the number of digits in v, which is O(log₁₀ v). Since the maximum value in the array is M, the digit extraction takes at most O(log M) time. Therefore, the overall time complexity is O(n × log M), where n is the length of the array and M ≤ 10⁹ is the maximum value of elements in the array.

Space Complexity: O(D)

The algorithm uses a dictionary d to store the maximum value for each digit sum. The number of unique digit sums is bounded by the maximum possible digit sum D. For a number with maximum value M = 10⁹, it has at most 9 digits, and each digit can be at most 9. Therefore, the maximum digit sum D = 9 × 9 = 81. The dictionary can have at most D entries, resulting in a space complexity of O(D), where D ≤ 81.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Update the Hash Table After Finding a Pair

A common mistake is to update the answer when finding a matching digit sum but forgetting to update the hash table with the current number. This causes the algorithm to miss potentially better pairs.

Incorrect Implementation:

for num in nums:
    digit_sum = calculate_digit_sum(num)
  
    if digit_sum in digit_sum_to_max_value:
        max_pair_sum = max(max_pair_sum, digit_sum_to_max_value[digit_sum] + num)
    else:
        digit_sum_to_max_value[digit_sum] = num
    # Missing: Update even when digit_sum exists!

Why this fails: If we have nums = [18, 36, 54] where all have digit sum 9:

• After processing 18 and 36, we get pair sum 54
• When we reach 54, we don't update the hash table
• We miss the optimal pair (36, 54) with sum 90

Correct Solution:

for num in nums:
    digit_sum = calculate_digit_sum(num)
  
    if digit_sum in digit_sum_to_max_value:
        max_pair_sum = max(max_pair_sum, digit_sum_to_max_value[digit_sum] + num)
  
    # Always update to keep the maximum value for each digit sum
    digit_sum_to_max_value[digit_sum] = max(digit_sum_to_max_value[digit_sum], num)

2. Integer Overflow in Digit Sum Calculation

While less common in Python, using the wrong data type or calculation method can cause issues.

Problematic Approach:

# Converting to string might seem easier but can be inefficient
digit_sum = sum(int(digit) for digit in str(num))

Better Approach:

digit_sum = 0
while num > 0:
    digit_sum += num % 10
    num //= 10

The mathematical approach is more efficient and avoids string conversion overhead.

3. Not Handling the Case of No Valid Pairs

Forgetting to initialize the result to -1 or not properly checking if any valid pair was found.

Incorrect:

max_pair_sum = 0  # Wrong! Should be -1

Correct:

max_pair_sum = -1  # Correctly indicates "no valid pair found"

4. Using the Same Element Twice

While the hash table approach naturally avoids this, some alternative implementations might accidentally pair an element with itself.

Example to verify: For nums = [9], the algorithm should return -1, not 18 (9+9), since we need two different indices.