Track selections that fit the slot

Scenario

A music streaming app fills the gap before an ad break, the slot, with a block of tracks. Each track has a length in seconds, and you pick some of them for the block.

A block opens with its shortest track and closes with its longest. The other tracks play in between, in any order. The opening and closing tracks together must fit in the slot. You are asked how many different blocks fit.

Your task

Write count_fitting_selections(lengths, slot).

lengths[i] is the length in seconds of the track at position i.
A selection is any non-empty set of positions. Tracks are told apart by position, so two tracks of the same length are different tracks.
A selection fits when its shortest length plus its longest length is at most slot.
A selection of one track has the same shortest and longest length. It fits when twice that length is at most slot.
Return the number of selections that fit, modulo 1,000,000,007.

Examples

Example 1 (traced)#

text2 lines

Input:  lengths = [5, 2, 4, 1], slot = 7
Output: 12

Sort the lengths: [1, 2, 4, 5]. Pointers lo and hi start at the two ends. If the two lengths fit, every subset of the tracks after lo, up to hi, can join the track at lo.

lo	hi	Sum	Fits?	Added	Count after	Move
0	3	1 + 5 = 6	yes	2^3 = 8	8	lo becomes 1
1	3	2 + 5 = 7	yes	2^2 = 4	12	lo becomes 2
2	3	4 + 5 = 9	no	0	12	hi becomes 2
2	2	4 + 4 = 8	no	0	12	hi becomes 1, the walk ends

The walk counts 12 selections.

Example 2#

text2 lines

Input:  lengths = [4], slot = 8
Output: 1

The one track is both the shortest and the longest. Its sum is 4 + 4 = 8, which fits.

Example 3#

text2 lines

Input:  lengths = [6, 7], slot = 10
Output: 0

Even the track of length 6 on its own needs 6 + 6 = 12, which is over 10.

Constraints

1 ≤ lengths.length ≤ 100,000 (tracks in the pool)
1 ≤ lengths[i] ≤ 1,000,000 (seconds)
1 ≤ slot ≤ 2,000,000 (seconds)

What does n ≤ 10^5 tell you?

A pool of n tracks has 2^n - 1 non-empty selections. At n = 60 that is already about 10^18, and at n = 100,000 no computer can list them. The count must come from arithmetic, not from listing.

The count itself can be as large as 2^100,000, so the statement asks for it modulo 1,000,000,007. Sorting takes about n × log n ≈ 1.7 × 10^6 steps, and the walk after it takes at most 100,000.

Scenario

A music streaming app fills the gap before an ad break, the slot, with a block of tracks. Each track has a length in seconds, and you pick some of them for the block.

Your task

Write count_fitting_selections(lengths, slot).

lengths[i] is the length in seconds of the track at position i.
A selection is any non-empty set of positions. Tracks are told apart by position, so two tracks of the same length are different tracks.
A selection fits when its shortest length plus its longest length is at most slot.
A selection of one track has the same shortest and longest length. It fits when twice that length is at most slot.
Return the number of selections that fit, modulo 1,000,000,007.

Examples

Example 1 (traced)#

text2 lines

Input:  lengths = [5, 2, 4, 1], slot = 7
Output: 12

Sort the lengths: [1, 2, 4, 5]. Pointers lo and hi start at the two ends. If the two lengths fit, every subset of the tracks after lo, up to hi, can join the track at lo.

lo	hi	Sum	Fits?	Added	Count after	Move
0	3	1 + 5 = 6	yes	2^3 = 8	8	lo becomes 1
1	3	2 + 5 = 7	yes	2^2 = 4	12	lo becomes 2
2	3	4 + 5 = 9	no	0	12	hi becomes 2
2	2	4 + 4 = 8	no	0	12	hi becomes 1, the walk ends

The walk counts 12 selections.

Example 2#

text2 lines

Input:  lengths = [4], slot = 8
Output: 1

The one track is both the shortest and the longest. Its sum is 4 + 4 = 8, which fits.

Example 3#

text2 lines

Input:  lengths = [6, 7], slot = 10
Output: 0

Even the track of length 6 on its own needs 6 + 6 = 12, which is over 10.

Constraints

1 ≤ lengths.length ≤ 100,000 (tracks in the pool)
1 ≤ lengths[i] ≤ 1,000,000 (seconds)
1 ≤ slot ≤ 2,000,000 (seconds)

What does n ≤ 10^5 tell you?

A pool of n tracks has 2^n - 1 non-empty selections. At n = 60 that is already about 10^18, and at n = 100,000 no computer can list them. The count must come from arithmetic, not from listing.

The count itself can be as large as 2^100,000, so the statement asks for it modulo 1,000,000,007. Sorting takes about n × log n ≈ 1.7 × 10^6 steps, and the walk after it takes at most 100,000.