1498: Number-of-Subsequences-That-Satisfy-the-Given-Sum-Condition
Medium

table of contents

For this algorithm, since we need a way to track minimum and maximum element quickly, it makes sense to sort nums as, we do not care about maintaining the respective order.

Consequently, if we choose a viable starting and ending element, that implies that any subsequence containing between the starting and ending element is viable. Therefore, for each starting element, we should just find the largest ending element.

Then, if the starting element is at index l and the ending element is at index r, we have 2^(r-l) possible subsequences.

That implies that we should also pre-calculate all the possible powers of 2 for faster calculations (from repetitions).

code

class Solution {
public:
    const static int MOD = 1e9+7;
    int numSubseq(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());

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

        int l = 0, r = nums.size()-1;
        long long ans = 0;
        while (l <= r) {
            if (nums[l] + nums[r] > target) {
                --r;
            } else {
                ans = (ans + pows[r - l]) % MOD;
                ++l;
            }
        }
        return ans;
    }
};

complexity