Tìm giá trị số nguyên dương nhỏ nhất không thể được biểu diễn dưới dạng tổng của bất kỳ tập con nào của một mảng nhất định trong Python

Giả sử chúng ta có một mảng các số dương đã được sắp xếp, mảng này được sắp xếp theo thứ tự tăng dần, er phải tìm giá trị dương nhỏ nhất không được biểu diễn dưới dạng tổng các phần tử của bất kỳ tập con nào đã cho đặt. Chúng ta phải giải quyết vấn đề này trong O (n) thời gian.

Vì vậy, nếu đầu vào là A =[1, 4, 8, 12, 13, 17], thì đầu ra sẽ là 2.

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -

• n:=kích thước của A

• answer:=1

• đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện

  • nếu A [i] <=answer, thì

    • answer:=answer + A [i]

  • nếu không,

    • đi ra từ vòng lặp

• trả lại câu trả lời

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

def get_smallest_element(A):
   n = len(A)
   answer = 1
   for i in range (0, n ):
      if A[i] <= answer:
         answer = answer + A[i]
      else:
         break
   return answer
A = [1, 4, 8, 12, 13, 17]
print(get_smallest_element(A))

Đầu vào

[1, 4, 8, 12, 13, 17]

Đầu ra

2