Leetcode 2342: Max Sum of a Pair With Equal Sum of Digits
You are given an array
nums of positive integers. You need to find two indices i and j such that i != j, and the sum of digits of the numbers nums[i] and nums[j] is the same. Return the maximum sum of nums[i] + nums[j] that you can obtain over all valid pairs of indices. If no such pair exists, return -1.Problem
Approach
Steps
Complexity
Input: The input consists of an integer array `nums` of length `n` where `n` is between 1 and 10^5.
Example: nums = [28, 17, 45, 64, 23]
Constraints:
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
Output: Return the maximum sum of `nums[i] + nums[j]` for two indices `i` and `j` where the sum of the digits of `nums[i]` equals the sum of the digits of `nums[j]`. If no such pair exists, return `-1`.
Example: 93
Constraints:
Goal: The goal is to find pairs of integers whose sum of digits are the same, and return the maximum sum of such pairs.
Steps:
• For each number in the array, calculate the sum of its digits.
• Store the largest number encountered for each sum of digits.
• For each new number, if its sum of digits has been seen before, calculate the sum of the current number and the previously encountered number with the same sum of digits, and update the maximum sum if necessary.
Goal: The length of `nums` is at least 1 and at most 10^5, and each element in `nums` is a positive integer between 1 and 10^9.
Steps:
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
Assumptions:
• The input array is valid and contains positive integers.
• Input: nums = [28, 17, 45, 64, 23]
• Explanation: The sum of digits of 28 is 10, the sum of digits of 64 is 10 as well, so the pair (28, 64) gives the maximum sum of 93.
Approach: We calculate the sum of digits of each number in the array and then find the maximum sum for numbers that share the same sum of digits.
Observations:
• We can calculate the sum of digits of a number by repeatedly dividing by 10 and summing the remainders.
• The key observation is that we only need to track the largest numbers for each sum of digits.
Steps:
• Create a map to store the maximum number for each sum of digits.
• Iterate through the `nums` array and calculate the sum of digits for each number.
• For each sum of digits, check if there is already a number with the same sum. If so, calculate the sum of the two numbers and update the maximum sum.
Empty Inputs:
• The input array will not be empty according to the constraints.
Large Inputs:
• The solution should efficiently handle arrays of length up to 10^5.
Special Values:
• If no two numbers have the same sum of digits, the output should be -1.
Constraints:
• The numbers are positive and at most 10^9, so care must be taken to handle large numbers.
int maximumSum(vector<int>& nums) {
map<int, int> mp;
int ans = -1;
for(int x: nums) {
int sum = 0;
int tmp = x;
while(tmp > 0) {
sum += (tmp % 10);
tmp /= 10;
}
if(mp.count(sum)) {
ans = max(ans, x + mp[sum]);
mp[sum] = max(x, mp[sum]);
} else {
mp[sum] = x;
}
}
return ans;
}
1 : Initialization
int maximumSum(vector<int>& nums) {
The function `maximumSum` is initialized with a vector of integers `nums`.
2 : Variable Declaration
map<int, int> mp;
A map `mp` is declared to store the sum of digits as the key and the corresponding number as the value.
3 : Variable Declaration
int ans = -1;
The variable `ans` is initialized to -1 to keep track of the maximum sum.
4 : Loop Start
for(int x: nums) {
A loop is initiated to iterate over each element `x` in the vector `nums`.
5 : Variable Initialization
int sum = 0;
A variable `sum` is initialized to 0 to store the sum of digits of the current element `x`.
6 : Variable Initialization
int tmp = x;
The variable `tmp` is initialized with the value of `x` to compute the sum of its digits.
7 : Loop Start
while(tmp > 0) {
A while loop is started to iterate through each digit of `tmp`.
8 : Digit Extraction
sum += (tmp % 10);
The last digit of `tmp` is extracted and added to `sum`.
9 : Digit Extraction
tmp /= 10;
The last digit is removed from `tmp` by integer division by 10.
10 : Condition Check
if(mp.count(sum)) {
A condition checks if the sum of digits `sum` is already present in the map `mp`.
11 : Max Calculation
ans = max(ans, x + mp[sum]);
If the sum is found in the map, the maximum sum is updated using the current element `x` and the value stored in `mp[sum]`.
12 : Map Update
mp[sum] = max(x, mp[sum]);
The value in the map `mp` for the current `sum` is updated to be the larger of the current element `x` and the previous value.
13 : Condition Else
} else {
If the sum of digits is not found in the map, a new entry is added.
14 : Map Insertion
mp[sum] = x;
The value `x` is inserted into the map `mp` with `sum` as the key.
15 : Return Statement
return ans;
The function returns the value of `ans`, which holds the maximum sum of pairs with the same digit sum.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the length of the input array `nums`, as we iterate over the array once and perform a constant-time operation to calculate the sum of digits for each number.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) because we use a hashmap to store the largest number for each sum of digits.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus