ক্ষুদ্রতম ধনাত্মক পূর্ণসংখ্যার মান খুঁজুন যা পাইথনে প্রদত্ত অ্যারের কোনো উপসেটের যোগফল হিসাবে উপস্থাপন করা যায় না

ধরুন আমাদের কাছে ধনাত্মক সংখ্যার একটি সাজানো অ্যারে আছে, এই অ্যারেটি ঊর্ধ্বমুখী ক্রমে সাজানো হয়েছে, এর জন্য সবচেয়ে ছোট ধনাত্মক মানটি খুঁজে বের করতে হবে যা প্রদত্ত কোনো উপসেটের উপাদানের যোগফল হিসাবে উপস্থাপন করা যাবে না সেট আমাদের এই সমস্যাটি O(n) সময়ে সমাধান করতে হবে।

সুতরাং, যদি ইনপুটটি A =[1, 4, 8, 12, 13, 17] এর মত হয়, তাহলে আউটপুট হবে 2।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=A

  এর আকার

• উত্তর :=1

• 0 থেকে n রেঞ্জের জন্য, করুন

  • যদি 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]

আউটপুট

2