Question

2815. Max Pair Sum in an Array

中文文档

Description

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

Solutions

Solution 1: Enumeration

First, we initialize the answer variable $ans=-1$. Next, we directly enumerate all pairs $(nums[i], nums[j])$ where $i \lt j$, and calculate their sum $v=nums[i] + nums[j]$. If $v$ is greater than $ans$ and the largest digit of $nums[i]$ and $nums[j]$ are the same, then we update $ans$ with $v$.

The time complexity is $O(n^2 \times \log M)$, where $n$ is the length of the array and $M$ is the maximum value in the array.

class Solution:
  def maxSum(self, nums: List[int]) -> int:
    ans = -1
    for i, x in enumerate(nums):
      for y in nums[i + 1 :]:
        v = x + y
        if ans < v and max(str(x)) == max(str(y)):
          ans = v
    return ans

class Solution {
  public int maxSum(int[] nums) {
    int ans = -1;
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        int v = nums[i] + nums[j];
        if (ans < v && f(nums[i]) == f(nums[j])) {
          ans = v;
        }
      }
    }
    return ans;
  }

  private int f(int x) {
    int y = 0;
    for (; x > 0; x /= 10) {
      y = Math.max(y, x % 10);
    }
    return y;
  }
}

class Solution {
public:
  int maxSum(vector<int>& nums) {
    int ans = -1;
    int n = nums.size();
    auto f = [](int x) {
      int y = 0;
      for (; x; x /= 10) {
        y = max(y, x % 10);
      }
      return y;
    };
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        int v = nums[i] + nums[j];
        if (ans < v && f(nums[i]) == f(nums[j])) {
          ans = v;
        }
      }
    }
    return ans;
  }
};

func maxSum(nums []int) int {
  ans := -1
  f := func(x int) int {
    y := 0
    for ; x > 0; x /= 10 {
      y = max(y, x%10)
    }
    return y
  }
  for i, x := range nums {
    for _, y := range nums[i+1:] {
      if v := x + y; ans < v && f(x) == f(y) {
        ans = v
      }
    }
  }
  return ans
}

function maxSum(nums: number[]): number {
  const n = nums.length;
  let ans = -1;
  const f = (x: number): number => {
    let y = 0;
    for (; x > 0; x = Math.floor(x / 10)) {
      y = Math.max(y, x % 10);
    }
    return y;
  };
  for (let i = 0; i < n; ++i) {
    for (let j = i + 1; j < n; ++j) {
      const v = nums[i] + nums[j];
      if (ans < v && f(nums[i]) === f(nums[j])) {
        ans = v;
      }
    }
  }
  return ans;
}