2342. Max Sum of a Pair With Equal Sum of Digits

MediumArrayHash TableSortingHeap (Priority Queue)
Leetcode Link

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:

  1. We calculate the sum of digits y.
  2. If y is already in the dictionary d, 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 number d[y].
    • Compare it with the current known maximum ans and update ans if the new potential maximum is greater.
  3. Regardless of whether y was already present or not, we update the dictionary with the highest value v for the sum of digits y. We use max(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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

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:

  1. Initialize ans as -1. This will store the eventual maximum sum nums[i] + nums[j] if a valid pair is found. If no valid pairs are found, ans will return -1.
  2. Initialize a defaultdict named d to store pairs of (sum of digits: maximum number with that sum).
  3. Iterate over each number v in the input nums array.
    • Calculate the sum of the digits y of the current number v using a while loop that adds v % 10 to y and then floor divides v by 10. This loop effectively extracts and sums up each digit of the number.
    • If the sum of digits y is already a key in the dictionary d, 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 with ans. Update ans with this new maximum if it is greater.
    • Update the dictionary with the key y by ensuring it stores the maximum v: 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.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which data structure is used in a depth first search?

Example Walkthrough

Let's consider a small example using the array nums = [42, 33, 60].

  1. Initialize ans as -1.
  2. Initialize the hash map d as a defaultdict with the default type as int. It will hold the sum of digits as the key and the respective maximum number as the value.
  3. Start with the first number 42. The sum of its digits is 4 + 2 = 6. Since there is no entry in d with 6 as key, add it with d[6] = 42.
  4. Move to the next number 33. The sum of its digits is 3 + 3 = 6. There is already an entry with the sum 6, so we check if the sum of d[6] (which is 42) and 33 is greater than ans. The current sum is 42 + 33 = 75, so we update ans = 75. Then we update d[6] to be the max of 42 and 33, which is 42, so no change is required.
  5. Proceed to the last number 60. The sum of its digits is 6 + 0 = 6. Again, there's an entry for sum 6. We compute the potential new maximum which is d[6] (42) plus 60 equals 102, and since it is greater than the current ans (75), we update ans = 102. We then update d[6] with the new maximum number 60.

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
Not Sure What to Study? Take the 2-min Quiz：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Time and Space Complexity

Time Complexity

The time complexity of the given code can be analyzed by considering two major parts:

  1. Iterating through each number in the nums list.
  2. 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, where m is the maximum number of digits in a number of the nums list since the largest digit sum for a number with m digits would be 9 * m (if each digit is 9).
  • 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.

Fast Track Your Learning with Our Quick Skills Quiz:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Recommended Readings

Sorting Summary

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

Heap Fundamentals

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫