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
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:
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:
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
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:
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
Case | How to Handle |
---|---|
Empty or null input array | Return -1 immediately, as no pairs can be formed. |
Input array with only one element | Return -1, as a pair requires at least two elements. |
All numbers in the array have different digit sums | The solution should correctly identify that no pairs satisfy the condition and return -1. |
All numbers in the array have the same digit sum | The solution should find the two largest numbers and return their sum. |
Array with large numbers potentially leading to integer overflow when summing them | Use long data type to store sums to prevent integer overflow. |
Array contains duplicate numbers with the same digit sum | The 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. |