LeetCode Entry
2342. Max Sum of a Pair With Equal Sum of Digits
Max pairs sum with equal digits sum
2342. Max Sum of a Pair With Equal Sum of Digits medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/893
Problem TLDR
Max pairs sum with equal digits sum #medium
Intuition
Group numbers by digits sums, find two largest elements.
Approach
- the maximum key is 9 * 9 = 81
- shortest golf requires sorting, time degrades 300ms vs 14ms
Complexity
-
Time complexity: \(O(n)\), O(nlog(n)) for Kotlin golf
-
Space complexity: \(O(1)\), O(n) for golf
Code
fun maximumSum(nums: IntArray) = nums
.groupBy { "$it".sumOf { it - '0' } }.filter { it.value.size > 1 }
.maxOfOrNull { it.value.sorted().takeLast(2).sum() } ?: -1
pub fn maximum_sum(nums: Vec<i32>) -> i32 {
let (mut s, mut r) = (vec![0; 99], -1);
for x in nums {
let (mut k, mut n) = (0, x as usize);
while n > 0 { k += n % 10; n /= 10 }
if s[k] > 0 { r = r.max(s[k] + x) }; s[k] = s[k].max(x)
}; r
}
int maximumSum(vector<int>& nums) {
int s[99]{}, r = -1;
for (int x: nums) {
int k = 0, n = x; for (;n; n /= 10) k += n % 10;
r = max(r, s[k] ? s[k] + x : r);
s[k] = max(s[k], x);
} return r;
}