Taro Logo

Max Sum of a Pair With Equal Sum of Digits

Medium
Google logo
Google
1 view
Topics:
ArraysDynamic ProgrammingGreedy Algorithms

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


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What is the maximum possible value of an element in the `nums` array?
  2. Can the `nums` array be empty, and if so, what should the return value be?
  3. If multiple pairs have the same maximum sum, is any one of them acceptable?
  4. Are all the numbers in the `nums` array guaranteed to be positive integers?
  5. What is the expected behavior if only one number in the array has a specific digit sum; should it return -1, or is there another defined behavior?

Brute Force Solution

Approach

The brute force strategy here is pretty straightforward: we're going to look at every single pair of numbers from the given list. For each pair, we'll check if they meet our condition, and if they do, we'll see if their sum is the biggest we've found so far.

Here's how the algorithm would work step-by-step:

  1. Start by taking the very first number in the list.
  2. Pair it with every other number in the list, one at a time.
  3. For each pair, calculate the sum of the digits of the first number, and then calculate the sum of the digits of the second number.
  4. Check if the two digit sums are equal. If they aren't, move on to the next pair.
  5. If the digit sums are equal, add the two numbers together.
  6. Compare this sum to the largest sum we've found so far. If it's bigger, remember this new sum as the largest.
  7. Now, move on to the second number in the original list.
  8. Pair it with every other number in the list (including the first number).
  9. Repeat the digit sum calculations, comparison, and largest sum tracking as before.
  10. Continue this process, going through each number in the original list and pairing it with every other number.
  11. After you've checked all possible pairs, the largest sum you've kept track of is your answer.

Code Implementation

def max_sum_of_pair_equal_sum_of_digits(numbers):
    maximum_sum = -1

    # Iterate through each number
    for first_index in range(len(numbers)):
        for second_index in range(first_index + 1, len(numbers)): 

            # Consider each pair only once
            first_number = numbers[first_index]
            second_number = numbers[second_index]

            first_number_digit_sum = calculate_digit_sum(first_number)
            second_number_digit_sum = calculate_digit_sum(second_number)

            # Only process pairs with equal digit sums
            if first_number_digit_sum == second_number_digit_sum:

                current_sum = first_number + second_number

                # Update maximum_sum if current_sum is greater
                if current_sum > maximum_sum:
                    maximum_sum = current_sum

    return maximum_sum

def calculate_digit_sum(number):
    digit_sum = 0
    number_string = str(number)
    for digit_character in number_string:
        digit_sum += int(digit_character)
    return digit_sum

Big(O) Analysis

Time Complexity
O(n²)The provided solution iterates through each of the n numbers in the input list. For each of these numbers, it compares it with every other number in the list, resulting in nested loops. Calculating the digit sum for each number in a pair takes constant time. Therefore, the dominant operation is the pairwise comparison, which occurs approximately n * (n-1) / 2 times. This simplifies to O(n²).
Space Complexity
O(1)The brute force algorithm, as described, does not use any auxiliary data structures that scale with the input size N (the number of elements in the input list). It only uses a few constant space variables: one to store the current maximum sum found so far, and others to iterate through the input array (indices). Therefore, the auxiliary space used is constant and independent of the input size N.

Optimal Solution

Approach

The core idea is to group numbers by the sum of their digits. Then, for each group, we want to find the two largest numbers and add them together to check for the maximum sum. This avoids comparing numbers that can never be a valid pair.

Here's how the algorithm would work step-by-step:

  1. Calculate the digit sum for each number in the given set.
  2. Organize the numbers into groups based on their digit sums. For example, all numbers with a digit sum of 5 will be in the same group.
  3. Within each group, identify the two largest numbers. If a group has fewer than two numbers, skip it.
  4. Add the two largest numbers together for each group to get a potential maximum sum.
  5. Compare the potential maximum sums from each group and keep track of the highest one.
  6. The highest sum found is the answer. If no group had at least two numbers, the answer is defined to be some default value like -1.

Code Implementation

def max_sum_of_pair_with_equal_sum_of_digits(numbers):
    digit_sum_to_numbers = {}
    maximum_sum = -1

    for number in numbers:
        digit_sum = 0
        temp_number = number
        while temp_number > 0:
            digit_sum += temp_number % 10
            temp_number //= 10

        # Group numbers by their digit sum.
        if digit_sum not in digit_sum_to_numbers:
            digit_sum_to_numbers[digit_sum] = []
        digit_sum_to_numbers[digit_sum].append(number)

    for digit_sum in digit_sum_to_numbers:
        numbers_with_equal_digit_sum = digit_sum_to_numbers[digit_sum]

        # Need at least two numbers to form a pair.
        if len(numbers_with_equal_digit_sum) >= 2:

            numbers_with_equal_digit_sum.sort(reverse=True)

            # Get the two largest numbers.
            first_largest_number = numbers_with_equal_digit_sum[0]
            second_largest_number = numbers_with_equal_digit_sum[1]

            current_sum = first_largest_number + second_largest_number

            # Update the maximum sum if the current sum is larger.
            maximum_sum = max(maximum_sum, current_sum)

    return maximum_sum

Big(O) Analysis

Time Complexity
O(n)Let n be the number of elements in the input array. Calculating the digit sum for each number takes O(1) time because the numbers are bounded (at most 10^5), thus the digit sum calculation takes constant time. Grouping the numbers and finding the two largest numbers in each group involves iterating through the input array once, which is O(n). The comparison of the sums is done in constant time. Therefore, the dominant operation is iterating through the array, resulting in O(n) time complexity.
Space Complexity
O(N)The primary auxiliary space usage comes from grouping numbers based on their digit sums. In the worst-case scenario, each number in the input array of size N could have a unique digit sum, leading to N different groups. This requires storing each number in a separate group, thus creating a hash map (or similar data structure) with N entries. Therefore, the space complexity is O(N), where N is the number of elements in the input.

Edge Cases

CaseHow to Handle
Empty or null input arrayReturn -1 immediately, as no pairs can be formed.
Input array with only one elementReturn -1, as a pair requires at least two elements.
All numbers in the array have different digit sumsThe solution should correctly identify that no pairs satisfy the condition and return -1.
All numbers in the array have the same digit sumThe solution should find the two largest numbers and return their sum.
Array with large numbers potentially leading to integer overflow when summing themUse long data type to store sums to prevent integer overflow.
Array contains duplicate numbers with the same digit sumThe hashmap approach will correctly find the maximum sum by considering all pairs with equal digit sums, including duplicates.
Array with numbers having digit sums that are close to the maximum integer value, potentially causing overflow when comparing the sums.Using long for comparison should handle large values without overflow when finding the maximum sum.
Very large array, requiring efficient processing to avoid exceeding time limit.Using a hash map to store digit sum and the largest number with that digit sum enables O(n) time complexity.