Leetcode 1621 Solution

This article provides solution to leetcode question 1621 (number-of-subsequences-that-satisfy-the-given-sum-condition)
Categories:
Tags:
Access this page by simply typing in "lcs 1621" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition

Solution

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()

        l = 0
        r = len(nums) - 1

        ans = 0
        while l <= r:
            while l <= r and nums[l] + nums[r] > target:
                r -= 1

            if l > r:
                break

            ans += pow(2, r - l, 1000000007)

            l += 1

        return ans % 1000000007