Thêm phần tử vào mảng để tổng có thể đạt mọi giá trị trong JavaScript

Mô tả vấn đề

Chúng ta cần viết một hàm JavaScript nhận vào mảng số arr làm đối số đầu tiên và một số num làm đối số thứ hai.

Chúng ta phải, bằng cách thêm phần tử vào mảng, làm cho mảng có thể tạo ra bất kỳ tổng nào từ [0, num] (bao gồm cả hai đầu) bằng cách cộng các số cụ thể từ mảng. Hàm trả về số lượng tối thiểu các số cần thêm.

Ví dụ, nếu đầu vào là:

const arr = [1, 5, 10]; 
const sum = 20;

Thì đầu ra nên là:

const output = 2;

Giải thích đầu ra

Vì nếu thêm hai số (2 và 4) vào mảng, ta có thể đạt mọi tổng trong [0, 20].

Ví dụ minh họa

Mã thực hiện (tham lam):

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));

Đầu ra

Kết quả trong console sẽ là:

2