Number of Music Playlists - Practice Coding Problems

Number of Music Playlists - Problem

Your music player contains n different songs. You want to listen to goal songs (not necessarily different) during your trip. To avoid boredom, you will create a playlist so that:

Every song is played at least once
A song can only be played again only if k other songs have been played

Given n, goal, and k, return the number of possible playlists that you can create. Since the answer can be very large, return it modulo 10^9 + 7.

Input & Output

Example 1 — Basic Case

$ Input: n = 3, goal = 3, k = 1

› Output: 6

💡 Note: We have 3 songs and want a playlist of length 3. Each song must be played at least once, and we can't repeat a song until 1 other song has been played. Possible playlists: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].

Example 2 — Higher K Value

$ Input: n = 2, goal = 3, k = 0

› Output: 6

💡 Note: With k=0, we can repeat any song immediately. We have 2 songs, need length 3, both songs used at least once. Playlists: [1,1,2], [1,2,1], [1,2,2], [2,1,1], [2,1,2], [2,2,1].

Example 3 — Impossible Case

$ Input: n = 2, goal = 3, k = 3

› Output: 0

💡 Note: With k=3, we need to play 3 other songs before repeating. But we only have 2 songs total, so it's impossible to repeat any song in a playlist of length 3.

Constraints

1 ≤ n ≤ 100
1 ≤ goal ≤ 100
0 ≤ k < n

Visualization

Tap to expand

Understanding the Visualization

Input

n=3 songs, goal=3 length, k=1 cooldown

Constraints

Every song used once, can't repeat until k others played

Output

6 possible valid playlists

Key Takeaway

🎯 Key Insight: Use DP to count playlists by tracking length and unique songs used

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is to use dynamic programming where dp[i][j] represents the number of playlists of length i using exactly j unique songs. We transition by either adding a new song or repeating an existing one (if the k constraint allows). Best approach is Bottom-Up DP with Time: O(goal × n), Space: O(goal × n)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Brute Force	O(n^goal)	O(goal)	Try all possible playlist arrangements recursively
Memoization (Top-Down DP)	O(goal × 2^n × n^k)	O(goal × 2^n × n^k)	Cache results of recursive calls to avoid recomputation
Bottom-Up Dynamic Programming	O(goal × n)	O(goal × n)	Build solution iteratively using 2D DP table

Recursive Brute Force — Algorithm Steps

For each playlist position, try all valid songs
Recursively build remaining playlist
Count all valid complete playlists

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Empty

Begin with empty playlist, try first song

Recursive Build

For each position, try all valid songs

Count Valid

Count playlists where all n songs used

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007

int countPlaylists(int pos, int* usedSongs, int usedCount, int* lastKSongs, int lastKCount, int n, int goal, int k) {
    if (pos == goal) {
        return usedCount == n ? 1 : 0;
    }
    
    long long total = 0;
    for (int song = 0; song < n; song++) {
        int canUse = 1;
        for (int i = 0; i < lastKCount; i++) {
            if (lastKSongs[i] == song) {
                canUse = 0;
                break;
            }
        }
        
        if (canUse) {
            int newUsed[100];
            memcpy(newUsed, usedSongs, sizeof(int) * usedCount);
            int newUsedCount = usedCount;
            
            int alreadyUsed = 0;
            for (int i = 0; i < usedCount; i++) {
                if (usedSongs[i] == song) {
                    alreadyUsed = 1;
                    break;
                }
            }
            if (!alreadyUsed) {
                newUsed[newUsedCount++] = song;
            }
            
            int newLastK[100];
            int newLastKCount = lastKCount;
            if (newLastKCount == k) {
                for (int i = 0; i < k-1; i++) {
                    newLastK[i] = lastKSongs[i+1];
                }
                newLastK[k-1] = song;
            } else {
                memcpy(newLastK, lastKSongs, sizeof(int) * lastKCount);
                newLastK[newLastKCount++] = song;
            }
            
            total = (total + countPlaylists(pos + 1, newUsed, newUsedCount, newLastK, newLastKCount, n, goal, k)) % MOD;
        }
    }
    
    return total;
}

int solution(int n, int goal, int k) {
    int usedSongs[100] = {0};
    int lastKSongs[100] = {0};
    return countPlaylists(0, usedSongs, 0, lastKSongs, 0, n, goal, k);
}

int main() {
    int n, goal, k;
    scanf("%d", &n);
    scanf("%d", &goal);
    scanf("%d", &k);
    
    int result = solution(n, goal, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n^goal)

For each of goal positions, we try up to n songs recursively

✓ Linear Growth

Space Complexity

O(goal)

Recursion call stack depth equals playlist length

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler