โปรแกรมนับจำนวนตัวเลขที่ต้องเพิ่มเพื่อสร้างตัวเลขทั้งหมดตั้งแต่ 1 ถึง k ใน C++

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และค่าอีกค่าหนึ่งคือ k เราต้องหาจำนวนตัวเลขขั้นต่ำที่ต้องแทรกเข้าไปใน nums เพื่อให้สามารถสร้างตัวเลขใดๆ จากช่วง [1, k] โดยใช้ subset (เซตย่อย) ของ nums ได้

ตัวอย่าง

หากอินพุตคือ nums = [3, 5], k = 6 ผลลัพธ์จะเป็น 2 เนื่องจากเราต้องแทรก 1, 2 เพื่อให้สร้างได้ดังนี้:

• 1 = [1]
• 2 = [2]
• 3 = [3]
• 4 = [1, 3]
• 5 = [5]
• 6 = [1, 5]

ขั้นตอนการแก้ปัญหา

1. เรียงลำดับอาร์เรย์ nums
2. กำหนด sum := 0, next := 1, ret := 0
3. สำหรับแต่ละ i ใน nums:
   • วนลูป while next < i:
     • ถ้า sum >= k ให้ออกจากลูป
     • sum := sum + next
     • next := sum + 1
     • เพิ่ม ret ขึ้น 1
   • ถ้า sum >= k ให้ออกจากลูป
   • sum := sum + i
   • next := sum + 1
4. วนลูป while next <= k:
   • sum := sum + next
   • next := sum + 1
   • เพิ่ม ret ขึ้น 1
5. คืนค่า ret

การนำไปใช้ (Implementation)

#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;
}

อินพุต

[3, 5], 6

เอาต์พุต

2