Chúng tôi có một mảng các số nguyên dương được sắp xếp như thế này -
const arr = [1, 3, 6, 10, 11, 15];
Chúng tôi bắt buộc phải viết một hàm, chẳng hạn như findSmallest () nhận vào một mảng như vậy và trả về số nguyên dương nhỏ nhất không thể được biểu diễn dưới dạng tổng của một số mảng con của mảng ban đầu này.
Ví dụ -
Đối với mảng được viết ở trên 2 là số nguyên dương nhỏ nhất không thể đạt được bằng cách cộng bất kỳ mảng con nào của mảng ban đầu này. Vì vậy, bây giờ chúng ta hãy viết mã cho hàm này. Khi mảng được sắp xếp, chúng ta có thể đạt được giải pháp cho vấn đề này trong thời gian tuyến tính. Ban đầu, chúng tôi nghĩ rằng số bắt buộc là 1, vì 1 là giá trị nhỏ nhất mà nó có thể nhận. Chúng tôi sẽ lặp qua mảng và tiếp tục thêm phần tử tương ứng vào số bắt buộc.
Nếu tại bất kỳ lần lặp nào, số tương ứng xảy ra lớn hơn số bắt buộc, có nghĩa là chúng tôi đã tìm thấy số cần thiết của mình, nếu không chúng tôi tiếp tục lặp lại.
Ví dụ
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)); Đầu ra
Đầu ra trong bảng điều khiển sẽ là -
2