Skip to content

Practice Max Sum of a Pair With Equal Sum of Digits

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Medium#2342
LeetCode Problem

Max Sum of a Pair With Equal Sum of Digits

Problem Statement

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. If no such pair of indices exists, return -1.

Source: Max Sum of a Pair With Equal Sum of Digits on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
nums = [18,43,36,13,7]
Output
54
Explanation

The digit sums are 9 for 18, 7 for 43, 9 for 36, 4 for 13 and 7 for 7. The eligible pairs are 18 + 36 = 54 in the digit-sum-9 group and 43 + 7 = 50 in the digit-sum-7 group. The group containing 13 has no partner. The answer is therefore 54. The two largest array values, 43 and 36, cannot be paired because their digit sums differ. When scanning, keep the largest previously seen value for each digit sum and compare before inserting the current value, ensuring distinct indices.

# Example 2

Input
nums = [10,12,19,14]
Output
-1
Explanation

The digit sums of 10, 12, 19 and 14 are 1, 3, 10 and 5 respectively. Each group has only one element, so no pair of distinct indices meets the condition. Return -1 rather than 0 or the largest input value. A number cannot pair with itself merely because its digit sum matches its own; a streaming implementation should look for an earlier element in the group before storing the current one.

Constraints

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9

How to solve Max Sum of a Pair With Equal Sum of Digits

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

Within a digit-sum group only the largest value matters as a partner, so one pass that remembers the best value seen so far per digit sum, comparing each new number against it before storing, finds the maximum pair without sorting.

Why brute force is not enough

Checking every pair i < j and computing both digit sums is O(n^2 * d); with nums.length up to 10^5 that is on the order of 10^10 digit operations.

Approach

  1. Note that values are at most 10^9, so digit sums are at most 82; a small fixed array indexed by digit sum replaces a hash map.
  2. Initialize the answer to -1 and every slot to empty.
  3. Scan nums once. Compute the digit sum of the current value; if its slot holds an earlier value, that value has a different index, so update the answer with their sum.
  4. Then store the larger of the slot's occupant and the current value. The invariant is that each slot holds the maximum element with that digit sum among the prefix seen so far, the only partner any later element needs.
  5. Return the answer, which stays -1 if no digit sum repeats.

Walkthrough of Example 1

nums = [18,43,36,13,7] → 54

  1. 18 has digit sum 9 and 43 has digit sum 7; both slots are empty, so store 18 and 43.
  2. 36 has digit sum 9; slot 9 holds 18, giving 18 + 36 = 54, the new answer. Slot 9 keeps max(18, 36) = 36.
  3. 13 has digit sum 4; store 13.
  4. 7 has digit sum 7; slot 7 holds 43, giving 50, which does not beat 54.
  5. The answer is 54.

Time and space

Time O(n log M) · Space O(1). Each of the n numbers has its digits summed in O(log M) steps, M being the largest value, and the table has at most 82 slots regardless of n.

Interview pitfalls

  • Pairing an element with itself; compare against the stored partner before storing the current value so indices stay distinct.
  • Returning 0 or the largest element when no valid pair exists instead of -1.
  • Sorting each group to take its top two, which is correct but adds O(n log n) time and per-group lists for no gain.
  • Rejecting duplicates: two equal values at different indices share a digit sum and form a legitimate pair.

Follow-up questions interviewers ask

  • How would you return the best pair sum for every digit-sum group rather than only the global best?
  • What changes if you need the best triple of indices with equal digit sums?
  • How would you maintain the answer in a stream where numbers both arrive and depart?

Further reading on the technique: Hash table

Related LeetCode Problems

Practice more problems similar to Max Sum of a Pair With Equal Sum of Digits.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.