We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Music Playlists

Difficulty: Hard

Problem Description

You have a music player with n different songs and want to create a playlist with goal songs. Each song must be played at least once, and a song can only be replayed if k other songs have been played since its last play. Return the number of possible playlists modulo 10^9 + 7.

Key Insights

  • Every song must be included at least once in the playlist.
  • A song can only be repeated after playing k different songs.
  • The problem can be approached using combinatorial mathematics and dynamic programming.

Space and Time Complexity

Time Complexity: O(n * goal)
Space Complexity: O(n * goal)

Solution

To solve this problem, we can use dynamic programming. We will create a 2D DP table where dp[i][j] represents the number of valid playlists of length j that contain exactly i different songs. The transitions will consider:

  1. Adding a new song that hasn't been played yet.
  2. Replaying a song that has been played before, ensuring that k other songs have been played since its last play.

The final answer will be found in dp[n][goal], which gives the number of playlists of length goal with all n songs used at least once.

Code Solutions

def numMusicPlaylists(n: int, goal: int, k: int) -> int:
    MOD = 10**9 + 7
    dp = [[0] * (goal + 1) for _ in range(n + 1)]
    dp[0][0] = 1  # Base case: 1 way to make empty playlist
    
    for j in range(1, goal + 1):
        for i in range(1, n + 1):
            # Adding a new song
            dp[i][j] += dp[i - 1][j - 1] * (n - (i - 1))
            dp[i][j] %= MOD
            
            # Replaying an old song
            if i > k:
                dp[i][j] += dp[i][j - 1] * (i - k)
                dp[i][j] %= MOD
                
    return dp[n][goal]
← Back to All Questions