2815

2815. Max Pair Sum in an Array (Easy)

You are given a 0-indexed integer array nums. You have to find the maximum sum of a pair of numbers from nums such that the maximum digit in both numbers are equal.

Return the maximum sum or -1 if no such pair exists.

 

Example 1:

Input: nums = [51,71,17,24,42]
Output: 88
Explanation: 
For i = 1 and j = 2, nums[i] and nums[j] have equal maximum digits with a pair sum of 71 + 17 = 88. 
For i = 3 and j = 4, nums[i] and nums[j] have equal maximum digits with a pair sum of 24 + 42 = 66.
It can be shown that there are no other pairs with equal maximum digits, so the answer is 88.

Example 2:

Input: nums = [1,2,3,4]
Output: -1
Explanation: No pair exists in nums with equal maximum digits.

 

Constraints:

• 2 <= nums.length <= 100
• 1 <= nums[i] <= 104

Solution 1.

// OJ: https://leetcode.com/problems/max-pair-sum-in-an-array
// Author: github.com/lzl124631x
// Time: O(NlogD)
// Space: O(1)
class Solution {
public:
    int maxSum(vector<int>& A) {
        int mx[10][2] = {}, ans = -1;
        for (int n : A) {
            int m = n, d = 0;
            for (; m; m /= 10) d = max(d, m % 10);
            if (n > mx[d][0]) mx[d][1] = mx[d][0], mx[d][0] = n;
            else if (n > mx[d][1]) mx[d][1] = n;
        }
        for (int d = 1; d <= 9; ++d) {
            if (mx[d][0] && mx[d][1]) ans = max(ans, mx[d][0] + mx[d][1]);
        }
        return ans;
    }
};