पायथन में गैर-खाली सबसेट गिनने का प्रोग्राम जहां न्यूनतम और अधिकतम तत्व का योग k से कम हो

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

इसलिए, यदि इनपुट nums = [2, 2, 5, 6], k = 7 जैसा है, तो आउटपुट 6 होगा, क्योंकि हम निम्नलिखित सबसेट बना सकते हैं: [2], [2], [2, 2], [2, 5], [2, 5], [2, 2, 5]।

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

• N := A का आकार
• सूची A को सॉर्ट करें
• ans := 0
• j := N - 1
• i के लिए 0 से N तक की रेंज में, करें
  • जब तक j और A[i] + A[j] > K, करें
    • j := j - 1
  • यदि i <= j और A[i] + A[j] <= K, तो
    • ans := ans + 2^(j - i)
• ans वापस करें

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

उदाहरण

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