पायथन में उस सबसे छोटे धनात्मक पूर्णांक को खोजें जिसे दिए गए ऐरे के किसी उपसमुच्चय के योग के रूप में प्रस्तुत नहीं किया जा सकता

मान लीजिए हमारे पास धनात्मक संख्याओं का एक सॉर्टेड ऐरे है, जो आरोही क्रम में सॉर्टेड है। हमें वह सबसे छोटा धनात्मक मान ढूंढना है जिसे दिए गए सेट के किसी भी उपसमुच्चय के तत्वों के योग के रूप में प्रस्तुत नहीं किया जा सकता। हमें इस समस्या को O(n) समय में हल करना है।

इसलिए, यदि इनपुट A = [1, 4, 8, 12, 13, 17] है, तो आउटपुट 2 होगा।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

• n := len(A)
• answer := 1
• i को 0 से n-1 तक के लिए:
  • यदि A[i] <= answer, तो answer := answer + A[i]
  • अन्यथा, लूप से बाहर निकलें।
• answer लौटाएं।

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

def get_smallest_element(A):
    n = len(A)
    answer = 1
    for i in range(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]

आउटपुट

2