Number of Subsequences That Satisfy the Given Sum Condition

Medium
771.

Number of Subsequences That Satisfy the Given Sum Condition

Number of Subsequences That Satisfy the Given Sum Condition is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google and Swiggy interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var numSubseq = function(nums, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Subsequences That Satisfy the Given Sum Condition Solution

Number of Subsequences That Satisfy the Given Sum Condition solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Number of Subsequences That Satisfy the Given Sum Condition is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google and Swiggy interviews.

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

Hints for Number of Subsequences That Satisfy the Given Sum Condition

  1. Hint 1

    Only the minimum and the maximum of a subsequence matter, so the order of nums is irrelevant — sort it.

  2. Hint 2

    Fix the smallest element; every larger element within the budget can be freely included or excluded.

  3. Hint 3

    If nums[lo] pairs with everything up to nums[hi], there are 2^(hi - lo) subsequences with nums[lo] as the minimum.

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

  1. Sort nums and precompute 2^i mod 10^9+7 for i up to n.
  2. Run lo from the left and hi from the right. While nums[lo] + nums[hi] > target, shrink hi.
  3. 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

Java

public static int numSubseq(int[] nums, int target) {
    final int MOD = 1000000007;
    int[] s = nums.clone();
    Arrays.sort(s);
    int n = s.length;
    long[] pow2 = new long[n];
    pow2[0] = 1;
    for (int i = 1; i < n; i++) pow2[i] = pow2[i - 1] * 2 % MOD;
    int lo = 0, hi = n - 1;
    long res = 0;
    while (lo <= hi) {
        if (s[lo] + s[hi] > target) hi--;
        else {
            res = (res + pow2[hi - lo]) % MOD;
            lo++;
        }
    }
    return (int) res;
}

C++

int numSubseq(vector<int>& nums, int target) {
    const long long MOD = 1000000007LL;
    vector<int> s = nums;
    sort(s.begin(), s.end());
    int n = (int) s.size();
    vector<long long> pow2(n, 1);
    for (int i = 1; i < n; i++) pow2[i] = pow2[i - 1] * 2 % MOD;
    int lo = 0, hi = n - 1;
    long long res = 0;
    while (lo <= hi) {
        if (s[lo] + s[hi] > target) hi--;
        else {
            res = (res + pow2[hi - lo]) % MOD;
            lo++;
        }
    }
    return (int) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms