অ-খালি উপসেট গণনা করার প্রোগ্রাম যেখানে পাইথনে সেটের সর্বনিম্ন এবং সর্বোচ্চ উপাদানের যোগফল k-এর থেকে কম

ধরুন আমাদের কাছে সংখ্যার একটি তালিকা আছে যাকে nums বলা হয় এবং আরেকটি মান k, আমাদেরকে খালি নয় এমন উপসেটের সংখ্যা S বের করতে হবে যাতে S এর min + সর্বাধিক S <=k। আমাদের মনে রাখতে হবে উপসেটগুলো মাল্টিসেট। সুতরাং, উপসেটগুলিতে ডুপ্লিকেট মান থাকতে পারে কারণ তারা তালিকার নির্দিষ্ট উপাদানগুলিকে নির্দেশ করে, মান নয়৷

সুতরাং, ইনপুট যদি nums =[2, 2, 5, 6], k =7 এর মত হয়, তাহলে আউটপুট হবে 6, আমরা নিম্নলিখিত উপসেটগুলি তৈরি করতে পারি যেমন:[2], [2], [2, 2], [2, 5], [2, 5], [2, 2, 5]।

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

• N :=A এর আকার
• তালিকা A সাজান
• উত্তর :=0
• j :=N - 1
• আমি 0 থেকে N রেঞ্জের জন্য, কর
  • যখন j এবং A[i] + A[j]> K, do
    • j :=j - 1
  • যদি i <=j এবং A[i] + A[j] <=K, তাহলে
    • উত্তর :=উত্তর + 2^(j - i)
• উত্তর ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

class Solution:
   def solve(self, A, K):
      N = len(A)
      A.sort()
      ans = 0
      j = N - 1
      for i in range(N):
         while j and A[i] + A[j] > K:
            j -= 1
            if i <= j and A[i] + A[j] <= K:
               ans += 1 << (j - i)
      return ans
ob = Solution()
nums = [2, 2, 5, 6]
k = 7 print(ob.solve(nums, k))

ইনপুট

[2, 2, 5, 6]

আউটপুট

6