गैर-रिक्त उपसमुच्चय को गिनने का कार्यक्रम जहां न्यूनतम और अधिकतम तत्व का योग पायथन में k से कम है

मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है और दूसरा मान k है, हमें गैर-रिक्त उपसमुच्चय S की संख्या इस प्रकार ज्ञात करनी है कि S का न्यूनतम + S का अधिकतम <=k। हमें यह ध्यान रखना होगा कि उपसमुच्चय मल्टीसेट होते हैं। इसलिए, सबसेट में डुप्लिकेट मान हो सकते हैं क्योंकि वे सूची के विशिष्ट तत्वों को संदर्भित करते हैं, मानों को नहीं।

इसलिए, यदि इनपुट संख्या =[2, 2, 5, 6], के =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
  • अगर मैं <=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