ปัญหา
กำหนดอาร์เรย์ arr และ target sum หาจำนวนน้อยที่สุดของตัวเลขที่ต้องเพิ่มเข้าไป เพื่อให้สามารถสร้างผลรวมได้ทุกค่าใน [0, target]
ตัวอย่าง
arr = [1, 5, 10], target = 20 เพิ่ม 2 และ 4 -> สร้างได้ทุกค่า 0-20 -> output: 2
ตัวอย่างโค้ด
const arr = [1, 5, 10];
const sum = 20;
const minimumAddition = (arr = [], sum = 1) => {
let canAdd = 1;
let count = 0, i = 0;
while (canAdd <= sum) {
if ((i >= arr.length) || (canAdd < arr[i])) {
count++;
canAdd += canAdd;
} else {
canAdd += arr[i++];
}
}
return count;
};
console.log(minimumAddition(arr, sum));
ผลลัพธ์
2
คำอธิบาย
Greedy: canAdd = ค่าสูงสุดที่สร้างได้ติดต่อกันจาก 0 จนถึงปัจจุบัน
หาก arr[i] <= canAdd: เพิ่ม arr[i] เข้าไป -> สร้างได้ถึง canAdd + arr[i]
หาก arr[i] > canAdd (หรือ arr หมด): ต้องเพิ่ม canAdd เอง (patch) -> canAdd *= 2
Time: O(n log target), Space: O(1)
เป็นปัญหา "Patching Array" (LeetCode 330)
