Welcome to Subscribe On Youtube

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.

• Java
• C++
• Python
• Go
• TypeScript

• 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;
      }
  };
  

• 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
  
  

• 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;
  }
  
  

All Problems

All Solutions