Tap here to switch tabs
Problem
Submissions

Problem: Number of Subsequences That Satisfy the Sum Condition

Number of Subsequences That Satisfy the Sum Condition counts nonempty subsequences of an integer array whose minimum and maximum values sum to at most a target, with the count modulo a large prime.

Statement

Given an integer array nums and an integer target, count how many non empty subsequences of nums satisfy the following condition: if minVal is the minimum element in the subsequence and maxVal is the maximum element in the subsequence, then minVal + maxVal <= target.

Return the number of such subsequences modulo 109+710^9 + 7.

Constraints:

  • 1≤1 \leq nums.length ≤105\leq 10^5

  • 1≤1 \leq nums[i] ≤106\leq 10^6

  • 1≤1 \leq target ≤106\leq 10^6

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Number of Subsequences That Satisfy the Sum Condition

Number of Subsequences That Satisfy the Sum Condition counts nonempty subsequences of an integer array whose minimum and maximum values sum to at most a target, with the count modulo a large prime.

Statement

Given an integer array nums and an integer target, count how many non empty subsequences of nums satisfy the following condition: if minVal is the minimum element in the subsequence and maxVal is the maximum element in the subsequence, then minVal + maxVal <= target.

Return the number of such subsequences modulo 109+710^9 + 7.

Constraints:

  • 1≤1 \leq nums.length ≤105\leq 10^5

  • 1≤1 \leq nums[i] ≤106\leq 10^6

  • 1≤1 \leq target ≤106\leq 10^6