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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Music Playlists

Number: 956

Difficulty: Hard

Paid? No

Companies: Amazon, Coursera

Problem Description

Given n different songs, determine the number of playlists of length goal that can be created such that every song is played at least once and a song can be replayed only if k other songs have been played between its consecutive occurrences. The answer should be returned modulo 10^9 + 7.

Key Insights

  • Use dynamic programming where dp[i][j] represents the number of ways to form a playlist of length i using exactly j distinct songs.
  • When adding a new song, multiply by the number of songs not yet used.
  • When reusing a song, ensure that at least k other distinct songs have been played before it can be repeated. This gives a factor of max(j - k, 0).
  • The recurrence relation becomes:
    dp[i][j] = dp[i-1][j-1]*(n - (j-1)) + dp[i-1][j]*max(j - k, 0)
  • Base case: dp[0][0] = 1, meaning an empty playlist uses 0 songs in one way.
  • The final answer is dp[goal][n].

Space and Time Complexity

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

Solution

We solve the problem using dynamic programming with a two-dimensional dp table where dp[i][j] denotes the number of ways to form a playlist of length i using j distinct songs. There are two cases for each step:

  1. Adding a brand-new song: There are (n - j + 1) choices.
  2. Reusing a song that has already been played (if j > k): There are max(j - k, 0) choices. We iterate over the length of the playlist from 1 to goal and for each possible count of distinct songs from 1 to n. The modulo operation is applied at every step to keep numbers within bounds. This approach leverages a straightforward DP formulation to build the solution iteratively.

Code Solutions

MOD = 10**9 + 7

def numMusicPlaylists(n, goal, k):
    # Create a DP table with dimensions (goal+1) x (n+1)
    dp = [[0] * (n + 1) for _ in range(goal + 1)]
    dp[0][0] = 1  # Base case: 0 songs in 0 steps
    # Iterate over the playlist length
    for i in range(1, goal + 1):
        # Iterate over the number of distinct songs used
        for j in range(1, n + 1):
            # Adding a new song not used before
            dp[i][j] = dp[i - 1][j - 1] * (n - (j - 1)) % MOD
            # Reusing an old song, only if at least k songs are between plays
            dp[i][j] = (dp[i][j] + dp[i - 1][j] * max(j - k, 0)) % MOD
    return dp[goal][n]
    
# Example usage:
# print(numMusicPlaylists(3, 3, 1))
← Back to All Questions