Khắc phục mảng (Patching Array) trong C++

Cho mảng nums đã sắp xếp và số n. Có thể thêm số vào mảng sao cho mọi số trong [1, n] đều biểu diễn được dưới dạng tổng của một số phần tử trong mảng. Tìm số lượng phần tử cần thêm tối thiểu.

Ví dụ

nums = [1,4], n = 7

Ban đầu có thể tạo: 1, 4, 5. Thêm 2 → có thể tạo: 1,2,3,4,5,6,7. Cần thêm 1 số.

Thuật toán tham lam

Duy trì req = số nhỏ nhất CHƯA thể hiện được (ban đầu = 1).

• Nếu nums[i] ≤ req: dùng nums[i] để mở rộng phạm vi → req += nums[i], i++.
• Nếu req (hoặc hết mảng): bắt buộc thêm req vào mảng → req += req (gấp đôi phạm vi), patches++.
• Lặp cho đến khi req > n.

Chứng minh tính đúng đắn

Nếu đã tạo được tất cả số trong [1, req-1]:

• Thêm số x ≤ req → tạo được tới req-1+x.
• Thêm số req → KHÔNG tạo được req (lỗ hổng).

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        long long req = 1;
        int i = 0, ret = 0;
        while (req <= n) {
            if (i < nums.size() && nums[i] <= req) {
                req += nums[i];
                i++;
            } else {
                req += req; // thêm req
                ret++;
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1, 4};
    cout << ob.minPatches(v, 7);
    return 0;
}

Độ phức tạp

• Thời gian: O(m + log n) — m = độ dài mảng, log n lần gấp đôi.
• Không gian: O(1).

Input / Output

Input:  {1,4} n=7
Output: 1