2342. Max Sum of a Pair With Equal Sum of Digits
Problem Description
This problem presents us with an array nums
filled with positive integers, and our goal is to find two different indices i
and j
, where i
is not equal to j
, such that the sum of the digits of nums[i]
is equal to the sum of the digits of nums[j]
. Once such indices are found, we need to return the maximum value of the sum nums[i] + nums[j]
that we can obtain by considering all possible pairs of indices that meet the given condition.
To clarify, if we pick nums[i]
as "123" and nums[j]
as "51", both have the sum of digits equal to 6 and thus meet the criteria since 1+2+3 = 5+1.
Intuition
The immediate brute-force approach would be to compute the sum of digits for every pair of numbers in the array and then find the maximum pair that meets the criteria. However, this would be inefficient with a time complexity of O(n^2) which is not optimal for large arrays.
The given solution leverages hashing to optimize the process. It uses a dictionary (or hash map) to keep track of the highest value number v
for each unique sum of digits y
. This way, when a new number is processed, we can easily check if there is already a stored number with the same sum of digits using the hash map.
While iterating through the nums
array, for each number:
- We calculate the sum of digits
y
. - If
y
is already in the dictionaryd
, it means we have encountered another number previously with the same sum of digits. We can then:- Calculate a potential new maximum by adding the current number
v
and the stored numberd[y]
. - Compare it with the current known maximum
ans
and updateans
if the new potential maximum is greater.
- Calculate a potential new maximum by adding the current number
- Regardless of whether
y
was already present or not, we update the dictionary with the highest valuev
for the sum of digitsy
. We usemax(d[y], v)
to ensure we always keep the larger number for that sum of digits, which is crucial for maximizing the eventual sum of nums[i] + nums[j].
The result of this process is the maximum sum that can be formed under the given constraints, which the function returns. If no such pair exists, the answer remains as the initialized value of -1
.
Learn more about Sorting and Heap (Priority Queue) patterns.
Solution Approach
The implementation of the solution makes use of a hash map to efficiently track the maximum number encountered for each unique sum of digits. The Python code utilizes a defaultdict
from the collections
module which simplifies the management of default values for non-existing keys. The algorithm proceeds as follows:
- Initialize
ans
as-1
. This will store the eventual maximum sumnums[i] + nums[j]
if a valid pair is found. If no valid pairs are found,ans
will return-1
. - Initialize a
defaultdict
namedd
to store pairs of (sum of digits: maximum number with that sum). - Iterate over each number
v
in the inputnums
array.- Calculate the sum of the digits
y
of the current numberv
using a while loop that addsv % 10
toy
and then floor dividesv
by10
. This loop effectively extracts and sums up each digit of the number. - If the sum of digits
y
is already a key in the dictionaryd
, then there exists a different number with the same sum of digits encountered earlier. In this case:- Compute the possible new maximum sum
d[y] + v
and compare it withans
. Updateans
with this new maximum if it is greater.
- Compute the possible new maximum sum
- Update the dictionary with the key
y
by ensuring it stores the maximumv
:d[y] = max(d[y], v)
. This step is crucial since it is possible to encounter multiple numbers with the same sum of digits and we are only interested in storing the largest one for the pair-wise comparison.
- Calculate the sum of the digits
The data structure used is crucial for optimizing the time complexity of this problem. By using a hash map, accessing and updating the maximum number for a sum of digits is done in constant time, bringing the overall time complexity of the algorithm down to O(n * k), where n
is the number of elements in nums
and k
is the average number of digits in numbers within nums
. This is assuming that the hash map operations (insert and lookup) are O(1) on average.
At the end of the loop, ans
contains the maximum sum of nums[i] + nums[j]
where sums of their digits are equal or remains -1
if no such pair exists. This value is then returned as the answer.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example using the array nums = [42, 33, 60]
.
- Initialize
ans
as-1
. - Initialize the hash map
d
as adefaultdict
with the default type as int. It will hold the sum of digits as the key and the respective maximum number as the value. - Start with the first number
42
. The sum of its digits is4 + 2 = 6
. Since there is no entry ind
with 6 as key, add it withd[6] = 42
. - Move to the next number
33
. The sum of its digits is3 + 3 = 6
. There is already an entry with the sum 6, so we check if the sum ofd[6]
(which is42
) and33
is greater thanans
. The current sum is42 + 33 = 75
, so we updateans = 75
. Then we updated[6]
to be the max of42
and33
, which is42
, so no change is required. - Proceed to the last number
60
. The sum of its digits is6 + 0 = 6
. Again, there's an entry for sum 6. We compute the potential new maximum which isd[6]
(42
) plus60
equals102
, and since it is greater than the currentans
(75
), we updateans = 102
. We then updated[6]
with the new maximum number60
.
At the end of this process, ans
holds the value 102
, which is the maximum sum of nums[i] + nums[j]
with equal digit sums. Since no other pairs are left to be considered, we would return 102
as the result.
Solution Implementation
1from collections import defaultdict
2
3class Solution:
4 def maximumSum(self, nums: List[int]) -> int:
5 # Initialize the maximum sum as -1 (assuming no answer is found yet)
6 max_sum = -1
7 # Initialize a dictionary to store the maximum number for each digit sum
8 digit_sum_max_num = defaultdict(int)
9
10 # Iterate through each number in the given list
11 for num in nums:
12 # Calculate the sum of digits for the current number
13 digit_sum = 0
14 temp_num = num
15 while temp_num:
16 digit_sum += temp_num % 10
17 temp_num //= 10
18
19 # If the sum of digits has been seen before,
20 # check if the current number contributes to a larger max sum
21 if digit_sum in digit_sum_max_num:
22 max_sum = max(max_sum, digit_sum_max_num[digit_sum] + num)
23
24 # Update the maximum number for the current digit sum
25 digit_sum_max_num[digit_sum] = max(digit_sum_max_num[digit_sum], num)
26
27 # Return the maximum sum of two numbers having the same sum of digits
28 return max_sum
29
1class Solution {
2 public int maximumSum(int[] nums) {
3 // This variable will hold the answer, initialized to -1 as per the problem statement.
4 int maxPairSum = -1;
5 // This array will store the maximum number encountered for each digit sum.
6 int[] maxNumWithDigitSum = new int[100];
7
8 // Iterate through all the numbers in the input array.
9 for (int number : nums) {
10 int sumOfDigits = 0;
11 // Calculate the sum of digits of the current number.
12 for (int tempNumber = number; tempNumber > 0; tempNumber /= 10) {
13 sumOfDigits += tempNumber % 10;
14 }
15 // If there's already a number with the same digit sum encountered,
16 // check if the two numbers form a larger pair sum.
17 if (maxNumWithDigitSum[sumOfDigits] > 0) {
18 maxPairSum = Math.max(maxPairSum, maxNumWithDigitSum[sumOfDigits] + number);
19 }
20 // Update the array with the maximum number for the current digit sum.
21 maxNumWithDigitSum[sumOfDigits] = Math.max(maxNumWithDigitSum[sumOfDigits], number);
22 }
23 // Return the maximum pair sum of numbers with the same digit sum, else -1.
24 return maxPairSum;
25 }
26}
27
1class Solution {
2public:
3 // Function to calculate the maximum sum of a pair of numbers with the same sum of digits
4 int maximumSum(vector<int>& numbers) {
5 // Initialize a vector of vectors to group numbers by their digit sums (up to 81 for 99999, which is maximum 5*9)
6 vector<vector<int>> digitSumGroups(100);
7
8 // Iterate through each number to calculate their digit sums and group them
9 for (int& number : numbers) {
10 int digitSum = 0;
11 // Calculate the sum of digits for the current number
12 for (int value = number; value > 0; value /= 10) {
13 digitSum += value % 10;
14 }
15 // Add the number to its corresponding digit sum group
16 digitSumGroups[digitSum].emplace_back(number);
17 }
18
19 int maxPairSum = -1; // Initialize max pair sum as -1 to handle cases with no valid pair
20 // Iterate through all digit sum groups
21 for (auto& group : digitSumGroups) {
22 // Check if there are at least two numbers in the current digit sum group
23 if (group.size() > 1) {
24 // Sort the numbers within the current group in descending order
25 sort(group.rbegin(), group.rend());
26 // Update the maxPairSum with the sum of the top two numbers in the current group
27 maxPairSum = max(maxPairSum, group[0] + group[1]);
28 }
29 }
30 // Return the maximum pair sum found
31 return maxPairSum;
32 }
33};
34
1// Define the maxDigits value representing the maximum possible sum of digits which is 9*5=45
2const MAX_DIGITS_SUM = 45;
3
4// Function to calculate the sum of the digits of a number
5const sumOfDigits = (number: number): number => {
6 let digitSum = 0;
7 while (number > 0) {
8 digitSum += number % 10;
9 number = Math.floor(number / 10);
10 }
11 return digitSum;
12};
13
14// Function to calculate the maximum sum of a pair of numbers with the same sum of digits
15const maximumSum = (numbers: number[]): number => {
16 // Initialize an array to group numbers by their digit sums
17 const digitSumGroups: number[][] = Array.from({ length: MAX_DIGITS_SUM + 1 }, () => []);
18
19 // Group numbers by their digit sum
20 numbers.forEach(number => {
21 const digitSum = sumOfDigits(number);
22 digitSumGroups[digitSum].push(number);
23 });
24
25 let maxPairSum = -1; // Initialize max pair sum as -1 to indicate no valid pair yet
26
27 // Iterate through all digit sum groups to find the maximum pair sum
28 digitSumGroups.forEach(group => {
29 if (group.length > 1) {
30 // Sort the group in descending order
31 group.sort((a, b) => b - a);
32 // Update the maxPairSum with the sum of the two largest numbers in the current group
33 maxPairSum = Math.max(maxPairSum, group[0] + group[1]);
34 }
35 });
36
37 // Return the maximum pair sum found, or -1 if no valid pairs exist
38 return maxPairSum;
39};
40
41// The functions can now be used globally as part of the TypeScript codebase
42
Time and Space Complexity
Time Complexity
The time complexity of the given code can be analyzed by considering two major parts:
- Iterating through each number in the
nums
list. - Summing the digits of each number and updating the dictionary.
For the first part, iterating through the nums
list is O(n)
where n
is the length of nums
.
For the second part, we must consider the number of digits in each number for the summation of digits and updating the dictionary. The number of digits d
in a number v
is proportional to log10(v)
. Hence, summing the digits of a number takes O(d)
time where d
is the number of digits. Since for each number, we perform a digit sum and update the dictionary, the overall time complexity for this part is O(d * n)
.
Combining both parts, the total time complexity is O(n * d)
.
Note that if the input numbers have a bounded size (for example, they are all 32-bit integers), d
can be considered a constant, and the time complexity can be viewed as O(n)
.
Space Complexity
The space complexity is determined by the space required to store the d
dictionary which holds the maximum number encountered for each digit sum.
- The number of unique digit sums is at most
9*m
, wherem
is the maximum number of digits in a number of thenums
list since the largest digit sum for a number withm
digits would be9 * m
(if each digit is9
). - Each entry in the dictionary stores an integer value (which is constant space).
Thus, the space complexity is O(m)
, where m
represents the maximum number of digits across all numbers in nums
.
If we again assume the input numbers are all 32-bit integers, m
is a constant (10, since 2^31 - 1
has 10 digits), making the space complexity O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!