Chương trình đếm có bao nhiêu số nên được thêm vào để tạo 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ố được gọi là num và một giá trị khác là k. Chúng ta phải tìm số lượng số tối thiểu mà chúng ta cần chèn vào nums để chúng ta có thể tạo ra bất kỳ số nào từ [1, k] bằng cách sử dụng một số tập hợp con trong nums.

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

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• sắp xếp các số mảng
• sum:=0, next:=1, ret:=0
• cho tất cả tôi trong nums
  • trong khi tiếp theo
  • nếu sum> =k, thì:
    • ra khỏi vòng lặp
  • sum:=sum + next
  • tiếp theo:=sum + 1
  • (tăng ret thêm 1)
• nếu sum> =k, thì:
  • ra khỏi vòng lặp
• sum:=sum + i
• tiếp theo:=sum + 1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include
using namespace std;
class Solution {
   public:
   int solve(vector& 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 solve(vector& nums, int k) {
   return (new Solution())->solve(nums, k);
}

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

Đầu vào

[3, 5], 6

Đầu ra

2