We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Max Sum of a Pair With Equal Sum of Digits

Number: 2473

Difficulty: Medium

Paid? No

Companies: Amazon, Bloomberg, Meta, Microsoft, Nvidia

Problem Description

Given an array of positive integers, find two different elements such that the sum of their digits is equal and their combined value is maximized. If no such pair exists, return -1.

Key Insights

  • Calculate the digit sum for each number.
  • Use a hash table (dictionary) to group numbers by their digit sum.
  • Keep track of the maximum number encountered so far for each digit sum.
  • For each number, if a number with the same digit sum has been seen before, consider the sum of the two as a candidate.
  • Alternatively, group numbers by digit sum and then find the two largest numbers in each group.
  • The digit sum calculation runs in O(d) where d is the number of digits, negligible relative to n.

Space and Time Complexity

Time Complexity: O(n * d) ~ O(n), where d is the maximum number of digits (typically constant). Space Complexity: O(n), for storing the mapping of digit sums to numbers.

Solution

We iterate through the array and compute the digit sum for each number. We use a hash table that maps from a digit sum to the maximum number encountered with that sum. For every element, if there is already a number in the hash table with the same digit sum, we compute the sum of the current number and that maximum value, and update our result if it is greater than our current maximum sum. Then, we update the hash table with the greater of the current number or the stored maximum for that digit sum. In this way, we ensure that we have seen the best candidate for pairing with any future number with the same digit sum.

Code Solutions

# Function to compute the sum of digits of a number
def digit_sum(n):
    total = 0
    # Process each digit of the number
    while n:
        total += n % 10   # Add the last digit to total
        n //= 10          # Remove the last digit
    return total

def maximumSum(nums):
    max_sum = -1                   # Initialize result as -1 (no valid pair found yet)
    best_by_digit = {}             # Dictionary to store the best (maximum) number for each digit sum

    # Iterate through each number in the list
    for num in nums:
        current_sum = digit_sum(num)   # Compute the digit sum for the current number
        # If the current digit sum exists, try forming a pair
        if current_sum in best_by_digit:
            # Compute the sum of the current number with the best candidate seen so far
            potential_pair = num + best_by_digit[current_sum]
            # Update max_sum if this pair is better
            max_sum = max(max_sum, potential_pair)
        # Update the best candidate for this digit sum to be the maximum number seen so far
        best_by_digit[current_sum] = max(best_by_digit.get(current_sum, 0), num)
    return max_sum

# Example usage:
# print(maximumSum([18,43,36,13,7]))  # Expected output: 54
← Back to All Questions