A music app has a playlist of n tracks, numbered 0 through n - 1, that it replays on an endless loop: track 0, track 1, ..., track n - 1, track 0, track 1, ... forever. Track i lasts dur_i minutes. A listener wants to pick some starting point in this endless loop and listen to a run of one or more consecutive tracks — staying inside the same forward-moving loop and wrapping past the end of the playlist as many times as needed — whose total duration is exactly target minutes. Determine the smallest possible number of tracks such a run can have, or report that no run of consecutive tracks ever sums to exactly target minutes.
Line 1: two space-separated integers n and target. Line 2: n space-separated integers dur_0, dur_1, ..., dur_{n-1}.
Print a single integer: the minimum number of consecutive tracks, over the endless repetition of the playlist, whose durations sum to exactly target, or -1 if no such run exists.
Example 1
Input
3 5 2 3 1
Expected
2
Explanation
The playlist loops 2, 3, 1, 2, 3, 1, .... The very first two tracks played already total 2 + 3 = 5 minutes, matching the target exactly, so the shortest possible run is 2 tracks.
Example 2
Input
4 15 3 1 4 1
Expected
7
Explanation
One full pass through the playlist totals 3 + 1 + 4 + 1 = 9 minutes, so after the loop repeats once (9 minutes, 4 tracks) the listener still needs 15 - 9 = 6 more minutes. Starting the next stretch at track index 1 (duration 1) and playing three tracks — 1, 4, 1 — supplies exactly those 6 minutes. The full run is therefore one complete loop (4 tracks) plus that 3-track stretch, for 4 + 3 = 7 tracks total.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →