เรามีอาร์เรย์ของจำนวนเต็มบวกที่เรียงแล้วแบบนี้:
const arr = [1, 3, 6, 10, 11, 15];
เราต้องเขียนฟังก์ชัน findSmallest() ที่รับอาร์เรย์แบบนี้และคืนค่าจำนวนเต็มบวกเล็กที่สุดที่ไม่สามารถแทนเป็นผลรวมของซับอาร์เรย์ใดๆ ของอาร์เรย์ต้นฉบับได้
ตัวอย่างเช่น:
สำหรับอาร์เรย์ข้างต้น 2 คือจำนวนเต็มบวกเล็กที่สุดที่ไม่สามารถทำได้จากการบวกซับอาร์เรย์ใดๆ ของอาร์เรย์ต้นฉบับ ตอนนี้มาเขียนโค้ดกัน เนื่องจากอาร์เรย์เรียงแล้ว เราสามารถแก้ได้ใน linear time เราพิจารณาว่าตัวเลขที่ต้องการคือ 1 เริ่มต้น เพราะ 1 คือค่าต่ำสุดที่เป็นไปได้ เราจะวนลูปผ่านอาร์เรย์และบวกองค์ประกอบที่ตรงกันเข้าไปในตัวเลขที่ต้องการ
ถ้าในรอบไหนรอบหนึ่ง องค์ประกอบที่ตรงกันมากกว่าตัวเลขที่ต้องการ แสดงว่าเราพบคำตอบแล้ว มิฉะนั้นก็วนลูปต่อ
ตัวอย่างโค้ด
const arr = [1, 3, 6, 10, 11, 15];
const findSmallest = arr => {
let res = 1;
for (let ind = 0; ind < arr.length && arr[ind] <= res; ind++) {
res += arr[ind];
}
return res;
};
console.log(findSmallest(arr));
ผลลัพธ์
ผลลัพธ์ในคอนโซลจะเป็นดังนี้:
2
