1033MediumArrayTwo PointersBinary SearchSorting

Picking Parts Whose Extremes Stay Under a Cap

Tracked in this browser only

Trains the technique from

LeetCode 1498Number of Subsequences That Satisfy the Given Sum Condition

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def num_subseq(sizes: list[int], cap: int) -> int:

Java

public int numSubseq(int[] sizes, int cap)

The intended approach

Time O(n log n) for the sort, then one pass.Space O(n) for the sorted sizes and the powers.

Whether a pick is safe rests only on its smallest and largest size, never on anything in between. So the sizes may be sorted without changing the count, which makes the two extremes easy to reach. With the sizes in order, close in from both ends. When the sizes at the two ends come to at most the cap, then taking the left size together with any choice at all of the sizes strictly between the two ends is safe, since the left size is the smallest of the pick and nothing between exceeds the right one. There are two raised to the count between them of those, so add that and step the left end in. When the two ends come to more than the cap, the right size is too large to pair with anything at all still in play, so step the right end in. Every pick is counted exactly once, under its own smallest size, so nothing is double counted. The powers of two are worked out once up front, each taken to the remainder.

Pythonentry point: num_subseq

def num_subseq(sizes, cap):
    mod = 1000000007
    order = sorted(sizes)
    n = len(order)
    power = [1] * (n + 1)
    for at in range(1, n + 1):
        power[at] = power[at - 1] * 2 % mod
    total = 0
    lo = 0
    hi = n - 1
    while lo <= hi:
        if order[lo] + order[hi] <= cap:
            total = (total + power[hi - lo]) % mod
            lo += 1
        else:
            hi -= 1
    return total

The obvious version

Take every non-empty choice of positions in turn, find its smallest and largest size by walking the chosen positions, and count it when the two come to at most the cap. Costs two raised to the count of parts rather than a sort and one pass.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_num_subseq(sizes, cap):
    mod = 1000000007
    n = len(sizes)
    total = 0
    for mask in range(1, 1 << n):
        low = None
        high = None
        for at in range(n):
            if mask >> at & 1:
                value = sizes[at]
                if low is None or value < low:
                    low = value
                if high is None or value > high:
                    high = value
        if low + high <= cap:
            total = (total + 1) % mod
    return total

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in