Ctrl K

A Stretch of a Looping Playlist

Medium
The playlist tracks is on repeat: after the last track the first one plays again, forever. tracks[i] is the length of the i-th track. Pick a run of consecutive tracks from this endless stream whose lengths add up to exactly total. Return the fewest tracks such a run can have, or -1 if no run works.
Example 1
tracks=[4, 2, 5], total=9 → 2

The playlist loops: 4, 2, 5, 4, 2, 5, … The consecutive 5 and 4 add up to 9, which is two tracks.

Example 2
tracks=[3, 1], total=10 → -1

The tracks alternate 3, 1, 3, 1, … A run of even length sums to a multiple of 4 and a run of odd length to an odd number, so 10 is out of reach.

Example 3
tracks=[2, 2, 3], total=14 → 6

Two full loops add up to exactly 14, which is six tracks.

Constraints
  • 1 ≤ len(tracks) ≤ 10⁵
  • 1 ≤ tracks[i] ≤ 10⁵
  • 1 ≤ total ≤ 10⁹
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsWindows With an Exact Alarm Count MediumStretches With k Odd Numbers MediumTrim the Ends to a Target MediumShortest Stretch to the Goal MediumLongest Run with a Given Sum Medium
loading Python…
Input
tracks=[4, 2, 5], total=9
Expected
2

Run checks the first 3 tests in your browser. Submit checks all 117 tests on the server, hidden ones included.