Number of Subsequences That Satisfy the Given Sum Condition — Medium Problem & Solution

Count the non-empty subsequences of nums whose smallest and largest elements add up to at most target. Return the count modulo 10^9 + 7.

Difficulty: Medium
Topics: Arrays, Sorting, Two Pointers, Binary Search
Asked at: Amazon, Google, Swiggy
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Count the non-empty subsequences of nums whose smallest and largest elements add up to at most target.

Return the count modulo 10^9 + 7.

Example 1

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: [3], [3,5], [3,5,6] and [3,6] qualify.

Example 2

Input: nums = [3,3,6,8], target = 10
Output: 6
Explanation: The two 3s are distinguishable by position.

Example 3

Input: nums = [2,3,3,4,6,7], target = 12
Output: 61

Constraints

1 <= nums.length <= 100000
1 <= nums[i] <= 1000000
1 <= target <= 1000000

How to solve Number of Subsequences That Satisfy the Given Sum Condition

A subsequence is characterised by its min and max, which are unaffected by order — so sort. Then for a fixed minimum at index lo, the valid maxima form a prefix of the remaining elements, and every subset of the values strictly between them is allowed.

Approach

Sort nums and precompute 2^i mod 10^9+7 for i up to n.
Run lo from the left and hi from the right. While nums[lo] + nums[hi] > target, shrink hi.
Otherwise every subsequence whose minimum is nums[lo] and whose other elements come from lo+1 … hi is valid — that is 2^(hi - lo) of them. Add it and advance lo.

Why it works

After sorting, nums[lo] + nums[hi] <= target means every element in lo+1 … hi can join, because each is at most nums[hi]. The 2^(hi - lo) subsets of that window, each with nums[lo] forced in, are exactly the subsequences with that minimum. Since hi only moves left as lo moves right, the sweep is linear.

Complexity

Time — O(n log n)
Space — O(n)

Pitfalls

Enumerating subsets is exponential — the powers of two are the whole trick.
Computing 2^(hi-lo) with repeated multiplication inside the loop makes it O(n²); precompute the table.
lo <= hi, not lo < hi — a single-element subsequence is valid when 2 · nums[lo] <= target.

Reference solution

Python

from typing import List

def numSubseq(nums: List[int], target: int) -> int:
    MOD = 1000000007
    s = sorted(nums)
    n = len(s)
    pow2 = [1] * n
    for i in range(1, n):
        pow2[i] = pow2[i - 1] * 2 % MOD
    lo, hi, res = 0, n - 1, 0
    while lo <= hi:
        if s[lo] + s[hi] > target:
            hi -= 1
        else:
            res = (res + pow2[hi - lo]) % MOD
            lo += 1
    return res

JavaScript

var numSubseq = function(nums, target) {
    var MOD = 1000000007;
    var s = nums.slice().sort(function(a, b) { return a - b; });
    var n = s.length;
    var pow2 = [1];
    for (var i = 1; i < n; i++) pow2.push(pow2[i - 1] * 2 % MOD);
    var lo = 0, hi = n - 1, res = 0;
    while (lo <= hi) {
        if (s[lo] + s[hi] > target) hi--;
        else { res = (res + pow2[hi - lo]) % MOD; lo++; }
    }
    return res;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue