Number of Music Playlists
Hard · Dynamic Programming · Dynamic Programming · Combinatorics
Problem
Your music player holds n different songs. For a trip you want a playlist of exactly goal plays (a song may be played more than once), such that:
- every one of the n songs is played at least once, and
- a song can be played again only after k other songs have been played since its previous play.
Return the number of different playlists, modulo 10^9 + 7. Two playlists differ when some position plays a different song.
Examples
Input: n = 3, goal = 3, k = 1 Output: 6
Three plays for three songs: each song once, in any of 3! = 6 orders.
Input: n = 2, goal = 3, k = 0 Output: 6
Of the 2^3 = 8 sequences, the two that use only one song are out.
Input: n = 2, goal = 3, k = 1 Output: 2
A song cannot follow itself, so the playlist alternates: ABA or BAB.
Constraints
- 0 <= k < n <= goal <= 100
Approaches
- Build every playlist — time O(n^goal), space O(n + goal)
Follow-up
Inclusion–exclusion also solves it: playlists that use only a chosen set of m songs number m · (m-1) · ... · (m-k+1) · (m-k)^(goal-k), and alternating sums over the songs left out leave those that use every song. That gives O(n log goal) with modular inverses.
Related problems
Start free on Cariara · Coding problems · System design studio
