เพิ่มค่าลงอาเรย์เพื่อครอบคลุมช่วง 1 ถึง N ใน C++ (Patching Array)

ภาพรวมปัญหา

ให้อาเรย์ nums และตัวเลข n เพิ่มตัวเลขน้อยที่สุดเข้า nums เพื่อให้สร้างผลรวมได้ทุกค่าใน [1,n]

ตัวอย่าง

nums = [1,4], n = 7 → เพิ่ม 1 ตัว (คือ 2) → สร้างได้ 1,2,3,4,5,6,7

วิธีแก้ปัญหา: Greedy

รักษา req = ค่าที่เล็กที่สุดที่ยังสร้างไม่ได้
- ถ้า nums[i] ≤ req → ใช้ nums[i] ขยายได้เป็น req + nums[i]
- ถ้าไม่ → ต้องเพิ่ม req เอง (patch) ขยายได้เป็น req + req

โค้ด 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;
                ret++;
            }
        }
        return ret;
    }
};

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

ผลลัพธ์

1

การวิเคราะห์ความซับซ้อน

• เวลา: O(m + log n) — m = nums.size()
• พื้นที่: O(1)