পাইথনে দেওয়া সম শর্ত পূরণকারী সাবসিকোয়েন্সের সংখ্যা গণনা

একটি nums অ্যারে এবং একটি k মান দেওয়া আছে। আমাদের কাজ হলো nums-এর নন-খালি সাবসিকোয়েন্সগুলির মধ্যে কতটির ন্যূনতম এবং সর্বোচ্চ উপাদানের যোগফল k-এর চেয়ে কম বা সমান, সেটি বের করা। ফলাফল বড় হতে পারে, তাই ১০⁹ + ৭ দিয়ে মডুলো ফেরত দিতে হবে।

যেমন, nums = [4,6,7,8], k = 11 হলে আউটপুট ৪। কারণ vaid সাবসিকোয়েন্সগুলো: [4], [4,6], [4,6,7], [4,7]।

সমাধানের ধাপসমূহ

nums সর্ট করুন।
m := 10⁹ + 7
left := 0, right := nums-এর আকার - 1
res := 0
যখন left <= right:

যদি nums[left] + nums[right] > k হয়, তবে right := right - 1
অন্যথায়:

num_inside := right - left
res := (res + (2^num_inside mod m)) mod m
left := left + 1

res ফেরত দিন।

উদাহরণ

def solve(nums, k):
    nums.sort()
    m = 10**9 + 7
    left = 0
    right = len(nums) - 1
    res = 0
    while left <= right:
        if nums[left] + nums[right] > k:
            right -= 1
        else:
            num_inside = right - left
            res = (res + pow(2, num_inside, m)) % m
            left += 1
    return res

nums = [4,6,7,8]
k = 11
print(solve(nums, k))

ইনপুট

[4,6,7,8], 11