Number of Subsequences That Satisfy the Given Sum Condition

How it works

We precompute all powers of 2 up to n to avoid repeated exponentiation. The two pointer logic moves inward from both ends: if the current pair satisfies the constraint, count the subsequences and advance the left pointer; otherwise, shrink the right pointer.

Steps

1. Sort the array and precompute power[i] = 2^i mod (10^9 + 7) for i from 0 to n-1.
2. Use two pointers starting at both ends.
3. While left <= right:
   • If nums[left] + nums[right] <= target, add power[right - left] to res and increment left.
   • Otherwise, decrement right.
4. Return the total count.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(n)

Things to watch for

Forgetting to Sort the Array

The two-pointer and binary search approaches require a sorted array. Since we only care about the minimum and maximum values in each subsequence (not their order), sorting is valid and necessary. Forgetting to sort leads to incorrect results because the two-pointer logic assumes sorted order.

Integer Overflow in Power Calculation

Computing 2^(r-l) can produce astronomically large numbers. Using naive exponentiation without modular arithmetic causes overflow. You must use modular exponentiation or precompute powers with modulo applied at each step to avoid this issue.

Misunderstanding the Counting Formula

For a valid range from index l to r where nums[l] is the minimum, there are 2^(r-l) valid subsequences, not 2^(r-l+1). This is because we must include nums[l] (it's the minimum), but any subset of the remaining r-l elements can be included. Off-by-one errors in this exponent are common.

from typing import List

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        nums.sort()
        MOD = 1000000007
        res = 0
        l, r = 0, len(nums) - 1
        power = [1] * len(nums)

        for i in range(1, len(nums)):
            power[i] = (power[i - 1] * 2) % MOD

        while l <= r:
            if nums[l] + nums[r] <= target:
                res = (res + power[r - l]) % MOD
                l += 1
            else:
                r -= 1

        return res

class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int MOD = 1000000007;
        int res = 0, l = 0, r = nums.size() - 1;
        vector<int> power(nums.size(), 1);

        for (int i = 1; i < nums.size(); i++) {
            power[i] = (power[i - 1] * 2) % MOD;
        }

        while (l <= r) {
            if (nums[l] + nums[r] <= target) {
                res = (res + power[r - l]) % MOD;
                l++;
            } else {
                r--;
            }
        }

        return res;
    }
};