Chào các coder! 🚀 Đây là Loser1 từ Learning AI with Losers, và hôm nay chúng ta sẽ khám phá Ngày 35 trong chuỗi Thử Thách Leetcode Hằng Ngày! Hãy sẵn sàng vì bài toán hôm nay xoay quanh việc kết hợp số thông minh để vượt qua một ngưỡng giá trị. Bắt đầu thôi! 🎯

Input: nums = [2,11,10,1,3], k = 10
Output: 2
Giải thích: 
- Thao tác 1: Xóa phần tử 1 và 2, sau đó thêm 1 * 2 + 2 vào nums. Mảng trở thành [4, 11, 10, 3].
- Thao tác 2: Xóa phần tử 3 và 4, sau đó thêm 3 * 2 + 4 vào nums. Mảng trở thành [10, 11, 10].
Tại thời điểm này, tất cả các phần tử của nums đều lớn hơn hoặc bằng 10, vì vậy chúng ta dừng lại.
Có thể chứng minh rằng 2 là số thao tác tối thiểu cần thiết để tất cả các phần tử của mảng đều lớn hơn hoặc bằng 10.
    

Input: nums = [1,1,2,4,9], k = 20
Output: 4
Giải thích: 
- Sau thao tác 1, nums trở thành [2, 4, 9, 3].
- Sau thao tác 2, nums trở thành [7, 4, 9].
- Sau thao tác 3, nums trở thành [15, 9].
- Sau thao tác 4, nums trở thành [33].
Tại thời điểm này, tất cả các phần tử của nums đều lớn hơn 20, vì vậy chúng ta dừng lại.
Có thể chứng minh rằng 4 là số thao tác tối thiểu cần thiết để tất cả các phần tử của mảng đều lớn hơn hoặc bằng 20.
    

📌 Problem Overview

Bạn có một mảng số nguyên nums và một giá trị ngưỡng k. Trong mỗi bước, bạn có thể:

• Lấy hai số nhỏ nhất x và y.
• Xóa chúng khỏi mảng.
• Thêm giá trị mới min(x, y) * 2 + max(x, y) vào lại mảng.

Mục tiêu là thực hiện ít bước nhất để tất cả các phần tử trong mảng lớn hơn hoặc bằng k.

🔹 Ví dụ minh họa:

🎭 Hãy tưởng tượng ta có một đội quân lính tí hon cần phải hợp lực để đánh bại trùm cuối k! Chúng ta cần gộp các chiến binh yếu hơn lại để tạo ra những chiến binh mạnh hơn! ⚔️🔥

🔻 Input: nums = [2,11,10,1,3], k = 10

🔺 Quá trình hợp nhất:

1. Kết hợp 1 và 2 → tạo ra 1 * 2 + 2 = 4 → nums = [4,11,10,3].
2. Kết hợp 3 và 4 → tạo ra 3 * 2 + 4 = 10 → nums = [10,11,10].

✅ Kết quả: Chỉ cần 2 bước để tất cả các phần tử ≥ 10! 🎉

🧠 Intuition

Hãy tưởng tượng bạn đang chơi một trò chơi phải kết hợp hai số nhỏ nhất liên tục để mọi phần tử trong danh sách đạt ít nhất k. Điều này giống như pha chế thần dược, nơi những nguyên liệu yếu (số nhỏ) cần được tăng cường bằng cách trộn lẫn! 🧪✨

Cách tốt nhất? Luôn trộn hai nguyên liệu yếu nhất trước để tạo ra thành phần mạnh hơn. Đảm bảo chúng ta đạt ngưỡng yêu cầu hiệu quả.

📝 Approach – Hướng tiếp cận

1️⃣ Sử dụng Min-Heap để tối ưu hóa

✅ Bước 1: Thêm tất cả các phần tử vào Min-Heap. ✅ Bước 2: Trong khi top của heap nhỏ hơn k, ta liên tục lấy 2 phần tử nhỏ nhất và hợp nhất chúng theo công thức min(x, y) * 2 + max(x, y), sau đó thêm lại vào heap. ✅ Bước 3: Khi tất cả các phần tử trong heap đều >= k, ta dừng lại và trả về số bước đã thực hiện.

🔹 Độ phức tạp: Vì mỗi lần ta chỉ thao tác trên heap (log n), nên tổng thời gian chạy là O(n log n), đủ nhanh cho n lên đến 2 * 10^5!

🚀 Code Implementation – Hiện thực hóa giải thuật

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        // Dùng priority_queue dạng minHeap (sắp xếp tăng dần)
        priority_queue<long long, vector<long long>, greater<long long>> minHeap;
        
        for (int num : nums) {
            minHeap.push(num);
        }

        int cnt = 0;

        // Khi phần tử nhỏ nhất trong heap < k, ta cần tiếp tục gộp
        while (minHeap.top() < k) {
            if (minHeap.size() < 2) break; // Nếu còn 1 phần tử nhỏ hơn k, ta không thể kết hợp thêm

            // Lấy 2 phần tử nhỏ nhất
            long long x = minHeap.top(); minHeap.pop();
            long long y = minHeap.top(); minHeap.pop();

            // Tạo phần tử mới theo công thức
            long long newElement = x * 2 + y;

            // Thêm lại vào heap
            minHeap.push(newElement);
            cnt++;
        }

        return cnt;
    }
};

🎨 Visual Illustration – Minh họa trực quan

💡 Giả sử ta có nums = [1,1,2,4,9] với k = 20.

✅ Tổng cộng 4 bước để đạt k = 20! 🏆

⏳ Complexity Analysis – Phân tích độ phức tạp

• Heapify toàn bộ mảng: O(n log n)
• Mỗi bước hợp nhất lấy 2 phần tử & chèn vào heap: O(log n)
• Tổng số lần hợp nhất tối đa: O(n)
• Tổng thời gian chạy: O(n log n) 🚀

🎯 Key Takeaways – Những điểm rút ra

✅ Heap (Priority Queue) là lựa chọn tối ưu để quản lý và trích xuất hai phần tử nhỏ nhất một cách nhanh chóng.
✅ Chiến thuật “tham lam” giúp ta gộp các số nhỏ nhất trước, từ đó tối ưu hóa số bước thực hiện.
✅ Tư duy trực quan hóa giúp dễ dàng hiểu được cách thuật toán hoạt động.

🔗 Resources – Nguồn tham khảo

📌 Leetcode Problem: 3066. Minimum Operations to Exceed Threshold Value II
📌 Full bài giải trên Learning AI with Losers: Xem tại đây
📌 Facebook Fanpage cập nhật Leetcode hàng ngày: Learning AI with Losers

🚀 Hãy tiếp tục chiến đấu cùng Leetcode Daily Challenge nhé! Hẹn gặp lại các bạn ở Day 36! 💡🔥

CODE EDITOR

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