Number of Subsequences That Satisfy the Given Sum Condition
You are given an array of integers nums and an integer target.
Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element in the subsequence is less than or equal to target.
Since the answer may be too large, return it modulo 10^9 + 7.
Example 1
Input
nums = [3,5,6,7], target = 9Output
4There are 4 valid subsequences: [3], [3,5], [3,5,6], and [3,6].
Example 2
Input
nums = [3,3,6,8], target = 10Output
6There are 6 valid subsequences, counting repeated numbers as distinct positions: [3], [3], [3,3], [3,6], [3,6], and [3,3,6].
Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^6
- 1 <= target <= 10^6
Asked at 6 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.