মান ল করুন nums নামের একটি সংখ্যার তালিকা এবং k নামের একটি মান, আমাদের এমন নন-এম্পটি সাবসেট S-এর সংখ্যা খুঁজে বের করতে হবে যাতে min(S) + max(S) <= k। সাবসেটগুলো মাল্টিসেট হিসেবে বিবেচনা করতে হবে। তাই সাবসেটে ডুপ্লিকেট মান থাকতে পারে কারণ সেগুলো লিস্টের নির্দিষ্ট এলিমেন্ট বোঝায়, মান নয়।
যদি ইনপুট হয় nums = [2, 2, 5, 6], k = 7, তবে আউটপুট হবে ৬, কারণ নিচের সাবসেটগুলো বানানো যায়: [2], [2], [2, 2], [2, 5], [2, 5], [2, 2, 5]।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:
- N := A-এর আকার
- A তালিকাটি সাজান
- ans := 0
- j := N - 1
- i কে ০ থেকে 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
