Chương trình đếm số lượng số cần bổ sung để tạo ra tất cả các số từ 1 đến k trong C++

Giả sử chúng ta có một danh sách các số gọi là nums và một giá trị k. Chúng ta cần tìm số lượng tối thiểu các số cần chèn vào nums sao cho có thể tạo ra bất kỳ số nào trong khoảng [1, k] bằng cách sử dụng một tập con của nums.

Ví dụ, nếu đầu vào là nums = [3, 5], k = 6, thì kết quả sẽ là 2, vì ta phải chèn thêm 1, 2 để có thể tạo ra: 1 = [1], 2 = [2], 3 = [3], 4 = [1, 3], 5 = [5], 6 = [1, 5].

Giải thuật

1. Sắp xếp mảng nums.
2. Khởi tạo sum := 0, next := 1, ret := 0.
3. Duyệt qua từng phần tử i trong nums:
   • Trong khi next < i:
     • Nếu sum >= k thì thoát khỏi vòng lặp.
     • sum := sum + next
     • next := sum + 1
     • Tăng ret lên 1.
   • Nếu sum >= k thì thoát khỏi vòng lặp.
   • sum := sum + i
   • next := sum + 1
4. Trong khi next <= k:
   • sum := sum + next
   • next := sum + 1
   • Tăng ret lên 1.
5. Trả về ret.

Ví dụ triển khai

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

class Solution {
public:
    int solve(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int sum = 0;
        int next = 1;
        int ret = 0;
        for (int i : nums) {
            while (next < i) {
                if (sum >= k) break;
                sum += next;
                next = sum + 1;
                ret++;
            }
            if (sum >= k) break;
            sum += i;
            next = sum + 1;
        }
        while (next <= k) {
            sum += next;
            next = sum + 1;
            ret++;
        }
        return ret;
    }
};

int main() {
    vector<int> v = {3, 5};
    int k = 6;
    cout << solve(v, k);
    return 0;
}

Đầu vào

[3, 5], 6

Đầu ra

2