Cho mảng số nguyên dương đã sắp xếp. Viết hàm findSmallest() trả về số nguyên dương nhỏ nhất KHÔNG thể biểu diễn thành tổng của một mảng con nào.
Ví dụ: [1, 3, 6, 10, 11, 15] → 2 là số nhỏ nhất không thể tạo ra bằng tổng mảng con.
Giải thuật O(n): khởi tạo kết quả = 1. Duyệt mảng, nếu phần tử hiện tại ≤ kết quả thì cộng vào kết quả, ngược lại dừng 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));Kết quả
Đầu ra trong console sẽ là:
2