Show problems as
Classic problem #1498MediumArrayTwo PointersBinary SearchSorting

Number of Subsequences That Satisfy the Given Sum Condition

Real-world version: Picking Parts Whose Extremes Stay Under a Cap
Tracked in this browser only
Read Number of Subsequences That Satisfy the Given Sum Condition on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A bin holds parts whose sizes read sizes. A pick is any non-empty choice of parts taken by position, so two picks differ when the positions differ, even where the sizes match.

A pick is safe when its smallest size added to its largest size comes to at most cap. A pick of one part is safe when twice that size is at most the cap.

Return how many safe picks there are, given as the remainder after dividing by 1000000007.

Examples

Example 1

Input
sizes = [3, 5, 6, 7], cap = 9
Output
4

Sorted, the sizes read 3, 5, 6, 7. The safe picks are 3 alone, 3 with 5, 3 with 6, and 3 with 5 and 6. Anything holding the 7 needs its smallest at 2 or less, and anything without the 3 has its smallest at 5, which pairs with nothing here.

Example 2

Input
sizes = [1], cap = 1
Output
0

The only pick is the single part, whose smallest and largest are both 1, adding to two, which is over the cap.

Example 3

Input
sizes = [5, 5], cap = 10
Output
3

Either part alone comes to ten, exactly the cap, and so does the pick holding both, so all three picks are safe.

Constraints

  • 1 <= sizes.length <= 10^5
  • 1 <= sizes[i] <= 10^6
  • 1 <= cap <= 10^6

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def num_subseq(sizes: list[int], cap: int) -> int:
Java
public int numSubseq(int[] sizes, int cap)

More on the same topics