पायथन का उपयोग करके दिए गए योग शर्त को पूरा करने वाले सबसीक्वेंस की संख्या खोजने का प्रोग्राम

मान लीजिए हमारे पास nums नामक एक सरणी और दूसरा मान k है। हमें nums के गैर-खाली सबसीक्वेंस की संख्या ढूंढनी है जैसे कि उस पर न्यूनतम और अधिकतम तत्व का योग k से कम या बराबर हो। उत्तर बहुत बड़ा हो सकता है इसलिए उत्तर को 10^9 + 7 से मोडुलो वापस करें।

उदाहरण के लिए, यदि इनपुट nums = [4,6,7,8] k = 11 है, तो आउटपुट 4 होगा क्योंकि ऐसे सबसीक्वेंस हैं:

• [4], यहां न्यूनतम 4 है, अधिकतम 4 है, इसलिए 4+4 <= 11

• [4,6], यहां न्यूनतम 4 है, अधिकतम 6 है, इसलिए 4+6 <= 11

• [4,6,7], यहां न्यूनतम 4 है, अधिकतम 7 है, इसलिए 4+7 <= 11

• [4,7], यहां न्यूनतम 4 है, अधिकतम 7 है, इसलिए 4+7 <= 11

हल करने के चरण

• सूची nums को सॉर्ट करें

• m := 10^9 + 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

आउटपुट

4