Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

leetcode34.png

🌟 LeetCode Daily Challenge Day 34: Max Sum of a Pair With Equal Sum of Digits

9 7 4 LeetCode Daily Challenge Day 34 – February 12th, 2025 MEDIUM #2342. Digit Sum Duo 18 Σ=9 36 Σ=9 54 43 Σ=7 7 Σ=7 50 Hash Map Magic Key: Σ=9 [18, 36] Key: Σ=7 [43, 7] FIND YOUR DIGIT DUO! 🤝 Learning AI With Losers

💡 By Loser1 from Learning AI with Losers


🔥 Bạn có bao giờ thấy hai người xa lạ bỗng trở thành tri kỷ chỉ vì có cùng sở thích? Hôm nay, ta sẽ tìm kiếm những con số có “tâm hồn đồng điệu” – tức là có tổng chữ số bằng nhau – và kết hợp chúng để tạo ra giá trị lớn nhất có thể!

📌 Hãy tưởng tượng bạn đang trong một bữa tiệc, nơi mỗi người có một số điểm “hòa hợp” nhất định. Nhiệm vụ của bạn là tìm ra cặp đôi ăn ý nhất có điểm tổng hợp cao nhất! 🎉

Hôm nay chúng ta cùng nhau với loser1 sẽ chinh phục bài toán [2342. Max Sum of a Pair With Equal Sum of Digits] – một thử thách thú vị với cách tiếp cận khéo léo! 🚀

2342. Max Sum of a Pair With Equal Sum of Digits

Medium
Đã giải: 59.5K Công ty: Không rõ

Bạn được cung cấp một mảng nums gồm các số nguyên dương (0-indexed). Bạn có thể chọn hai chỉ số ij, sao cho i != j, và tổng các chữ số của số nums[i] bằng tổng các chữ số của nums[j].

Trả về giá trị lớn nhất của nums[i] + nums[j] mà bạn có thể đạt được với tất cả các cặp chỉ số ij thỏa mãn điều kiện.

Example 1:

Input: nums = [18,43,36,13,7]
Output: 54
Giải thích: Các cặp (i, j) thỏa mãn điều kiện là:
- (0, 2), cả hai số có tổng chữ số bằng 9, và tổng của chúng là 18 + 36 = 54.
- (1, 4), cả hai số có tổng chữ số bằng 7, và tổng của chúng là 43 + 7 = 50.
Vì vậy, tổng lớn nhất mà chúng ta có thể đạt được là 54.
    

Example 2:

Input: nums = [10,12,19,14]
Output: -1
Giải thích: Không có hai số nào thỏa mãn điều kiện, vì vậy chúng ta trả về -1.
    

Ràng buộc:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

🧠 Intuition

Bạn có bao giờ để ý rằng một số như 1836 đều có tổng chữ số là 9 không? 🤔

💡 Ý tưởng chính:

  1. Nhóm các số có tổng chữ số giống nhau (tức là những người có “tâm hồn tương đồng”).
  2. Chọn hai số lớn nhất từ mỗi nhóm để tạo thành cặp có tổng giá trị cao nhất.

📌 Minh họa trực quan
Giả sử ta có danh sách số như sau:

nums = [18, 43, 36, 13, 7]

Ta tính tổng chữ số của từng số:

  • 18 → 1 + 8 = 9
  • 43 → 4 + 3 = 7
  • 36 → 3 + 6 = 9
  • 13 → 1 + 3 = 4
  • 7 → 7

Bây giờ ta nhóm lại:

Tổng chữ số 9: [18, 36]
Tổng chữ số 7: [43, 7]
Tổng chữ số 4: [13]
Tổng chữ số 7: [7]

📌 Cặp có tổng giá trị cao nhất là (18, 36) → 54


🛠️ Approach

1️⃣ Duyệt qua danh sách và nhóm các số theo tổng chữ số

Sử dụng unordered_map<int, multiset<int>> để lưu các số có cùng tổng chữ số.

  • Key: Tổng chữ số
  • Value: Một tập hợp chứa các số tương ứng

2️⃣ Với mỗi nhóm, tìm hai số lớn nhất

Vì ta dùng multiset<int>, các số sẽ tự động được sắp xếp tăng dần.
📌 Ta chỉ cần lấy hai phần tử cuối cùng của tập hợp để tính tổng lớn nhất!


⏱️ Complexity

  • Time Complexity: O(nlog⁡n)O(n \log n) do mỗi lần chèn vào multiset mất O(log⁡n)O(\log n)
  • Space Complexity: O(n)O(n) vì ta lưu tất cả các số vào unordered_map

👨‍💻 Code Solution

C++
class Solution {
public:
    int sum_digits(int x) {
        int ans = 0;
        while (x > 0) {
            ans += x % 10;
            x /= 10;
        }
        return ans;
    }

    int maximumSum(vector<int>& nums) {
        int ans = -1;
        unordered_map<int, multiset<int>> myMap;  
        for (int x : nums) {
            myMap[sum_digits(x)].insert(x);
        }

        for (const auto& pair : myMap) {
            const multiset<int>& myMultiSet = pair.second;
            
            if (myMultiSet.size() >= 2) {  
                auto it = myMultiSet.rbegin();  
                int max1 = *it; 
                ++it;
                int max2 = *it;
                ans = max(ans, max1 + max2);
            }
        }

        return ans;
    }
};

🌈 Visualization

Hãy tưởng tượng mảng [18, 43, 36, 13, 7] như một nhóm bạn:

  • Nhóm tổng 9: 18 (9) 🤝 36 (9) → Tổng 54
  • Nhóm tổng 7: 43 (7) 🤝 7 (7) → Tổng 50
    → Kết quả là 54 – chính là sự kết hợp hoàn hảo của hai “người bạn” lớn nhất trong nhóm! 🏆

🎯 Key Takeaways

✔️ Nhóm số theo tổng chữ số giúp chúng ta tìm ra những “tri kỷ” số học.
✔️ Sử dụng multiset giúp dễ dàng lấy hai số lớn nhất.
✔️ Cách tiếp cận này hiệu quả hơn brute-force, tiết kiệm thời gian đáng kể.


🚀 Loser’s Wisdom of the Day:
“Trong lập trình (và cuộc sống), đôi khi bạn không cần phải tìm kiếm toàn bộ thế giới để có câu trả lời – chỉ cần nhìn vào những gì có chung bản chất với nhau!” 💡

🔥 Ngày mai chúng ta sẽ tiếp tục khám phá thế giới thuật toán! Đừng bỏ lỡ nhé! 💪

CODE EDITOR

📌 Hashtags:
#leetcode #leetcodedaily #coding #datastructures #algorithms #learningwithlosers

quyminhhuy0@gmail.com
quyminhhuy0@gmail.com
Articles: 49

Newsletter Updates

Enter your email address below and subscribe to our newsletter

Subscribe
Notify of
guest

0 Comments
Inline Feedbacks
View all comments
AI Assistant
Hi! How can I help you today?
Yıllık burç yorumları. As a result, we get the list of contacts sorted by name alphabetically.