Number of Subsequences That Satisfy the Given Sum Condition

medium array two pointers binary search sorting

Problem

Given nums and target, count non-empty subsequences where min + max ≤ target. Return modulo 10^9+7.

Inputnums=[3,5,6,7], target=9

Output4

[3], [3,5], [3,5,6], [3,6] — 4 valid subsequences.

nums

target

def num_subseq(nums, target):
    MOD = 10**9 + 7
    a = sorted(nums)
    n = len(a)
    pow2 = [1] * n
    for i in range(1, n): pow2[i] = pow2[i-1] * 2 % MOD
    l, r, ans = 0, n - 1, 0
    while l <= r:
        if a[l] + a[r] <= target:
            ans = (ans + pow2[r - l]) % MOD; l += 1
        else:
            r -= 1
    return ans

function numSubseq(nums, target) {
  const MOD = 1_000_000_007n;
  const a = nums.slice().sort((x, y) => x - y);
  const n = a.length, pow2 = new Array(n).fill(1n);
  for (let i = 1; i < n; i++) pow2[i] = pow2[i-1] * 2n % MOD;
  let l = 0, r = n - 1, ans = 0n;
  while (l <= r) {
    if (a[l] + a[r] <= target) { ans = (ans + pow2[r - l]) % MOD; l++; }
    else r--;
  }
  return Number(ans);
}

class Solution {
    public int numSubseq(int[] nums, int target) {
        long MOD = 1_000_000_007L;
        Arrays.sort(nums);
        int n = nums.length;
        long[] p = new long[n]; p[0] = 1;
        for (int i = 1; i < n; i++) p[i] = p[i-1] * 2 % MOD;
        int l = 0, r = n - 1; long ans = 0;
        while (l <= r) {
            if (nums[l] + nums[r] <= target) { ans = (ans + p[r - l]) % MOD; l++; }
            else r--;
        }
        return (int) ans;
    }
}

int numSubseq(vector& nums, int target) {
    long long MOD = 1000000007LL;
    sort(nums.begin(), nums.end());
    int n = nums.size();
    vector p(n, 1);
    for (int i = 1; i < n; i++) p[i] = p[i-1] * 2 % MOD;
    int l = 0, r = n - 1; long long ans = 0;
    while (l <= r) {
        if (nums[l] + nums[r] <= target) { ans = (ans + p[r - l]) % MOD; l++; }
        else r--;
    }
    return (int) ans;
}

Explanation

For a subsequence, only the smallest and largest chosen values decide whether min + max <= target. That observation lets us avoid checking every subset and instead just pick the smallest element and count how many companions are allowed.

We first sort the array so "smallest" and "largest" become "leftmost" and "rightmost". Then two pointers l and r walk inward. If a[l] + a[r] <= target, then a[l] is a valid minimum paired with a[r] as the maximum.

Here is the counting trick: once l is fixed as the minimum and r works as a max, every element strictly between them (there are r - l of them) can be freely included or excluded. That gives 2^(r - l) subsequences, which we add and then do l += 1. If the pair is too big, we shrink with r -= 1.

Powers of two are precomputed in pow2 and everything is taken modulo 10^9+7 to keep numbers small.

Example: nums = [3,5,6,7], target = 9. Sorted it stays the same. With l=0, r=3: 3+7=10 > 9 so r--. Then 3+6=9 <= 9 → add 2^2 = 4. The remaining pairs fail, so the answer is 4.

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