Python에서 주어진 배열의 하위 집합의 합으로 나타낼 수 없는 가장 작은 양의 정수 값 찾기

정렬된 양수 배열이 있다고 가정하고 이 배열은 오름차순으로 정렬되며 주어진 하위 집합의 요소 합계로 나타낼 수 없는 가장 작은 양수 값을 찾아야 합니다. 세트. O(n) 시간 안에 이 문제를 해결해야 합니다.

따라서 입력이 A =[1, 4, 8, 12, 13, 17]과 같으면 출력은 2가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=A의 크기
답 :=1
0에서 n 사이의 i에 대해 수행
- A[i] <=대답이면
  - 답변 :=답변 + A[i]
- 그렇지 않으면
  - 루프에서 나오다
답변을 반환

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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

입력

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