{x}
blog image

Max Sum of a Pair With Equal Sum of Digits

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.

 

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 <= 105
  • 1 <= nums[i] <= 109

Solution Explanation:

The problem asks to find the maximum sum of a pair of numbers in the input array nums where the sum of digits of both numbers are equal.

The most efficient approach uses a hash table (or a simple array in this case since the maximum possible sum of digits is relatively small). This avoids nested loops which would result in O(n^2) time complexity.

Algorithm:

  1. Initialization: Create a hash table (or array) d to store the maximum number encountered so far for each possible digit sum. Initialize all entries to 0. Also, initialize a variable ans to -1 (to handle the case where no such pair exists).

  2. Iteration: Iterate through the input array nums. For each number v:

    • Calculate the sum of its digits (x). This can be done efficiently using modular arithmetic.
    • Check if x already exists as a key in d. If it does, it means we've encountered a number before with the same digit sum. Update ans to the maximum of ans and the sum of v and the maximum number previously seen with the same digit sum (d[x]).
    • Update d[x] to the maximum of its current value and v. This ensures that d[x] always holds the largest number seen so far with digit sum x.

  3. Return: After iterating through all numbers, return ans.

Time Complexity Analysis:

  • Calculating the sum of digits for each number takes O(log M) time, where M is the maximum value in nums. This is because the number of digits in M is proportional to log10M.
  • Iterating through the array takes O(n) time, where n is the length of nums.
  • Hash table lookups and updates take O(1) on average.

Therefore, the overall time complexity is O(n log M). Since M is at most 109, log M is relatively small, making this approach very efficient.

Space Complexity Analysis:

The space complexity is determined by the size of the hash table d. The maximum sum of digits for a number less than 109 is 81 (9 digits each with a maximum value of 9). We can therefore use an array of size at most 82 (or 100 for simplicity to avoid boundary checking). This leads to a space complexity of O(1). The space used is constant regardless of the input size.

Code Examples (with explanations embedded):

The code examples in various languages provided earlier demonstrate this algorithm. The key parts are:

  • Digit Sum Calculation: The nested loop or iterative approach efficiently computes the digit sum.
  • Hash Table (or Array) Usage: The hash table (or array) d is used to efficiently store and retrieve the maximum number for each digit sum.
  • Maximum Sum Update: The ans variable is updated to track the maximum sum found so far.

The choice between using a hash table (dictionary in Python) or a fixed-size array depends on the programming language and whether the maximum sum of digits needs to be dynamically determined. Since the maximum digit sum is bounded, a fixed size array is more efficient in this particular problem.