Skip to content

920. Number of Music Playlists

DifficultyHard

Description

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 109 + 7.

 

Example 1:

Input: n = 3, goal = 3, k = 1
Output: 6
Explanation: There are 6 possible playlists: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], and [3, 2, 1].

Example 2:

Input: n = 2, goal = 3, k = 0
Output: 6
Explanation: There are 6 possible playlists: [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2, 1], [2, 1, 2], and [1, 2, 2].

Example 3:

Input: n = 2, goal = 3, k = 1
Output: 2
Explanation: There are 2 possible playlists: [1, 2, 1] and [2, 1, 2].

 

Constraints:

  • 0 <= k < n <= goal <= 100

Solutions

Solution 1: Dynamic Programming

Thinking

A playlist of length \(\textit{goal}\) must use exactly \(n\) distinct songs, and a repeat of the same song needs a gap of at least \(k\). \(\textit{goal},n\le 100\), so DP fits. \(f[i][j]\) is the number of lists of \(i\) songs using \(j\) distinct ones: \(n-j+1\) choices for a new song, and \(j-k\) for a repeat when \(j>k\). The answer is \(f[\textit{goal}][n]\).

We define \(f[i][j]\) to be the number of playlists that can be made from \(i\) songs with exactly \(j\) different songs. We have \(f[0][0] = 1\) and the answer is \(f[\textit{goal}][n]\).

For \(f[i][j]\), we can choose a song that we have not listened before, so the previous state is \(f[i - 1][j - 1]\), and there are \(n - (j - 1) = n - j + 1\) options. Thus, \(f[i][j] += f[i - 1][j - 1] \times (n - j + 1)\). We can also choose a song that we have listened before, so the previous state is \(f[i - 1][j]\), and there are \(j - k\) options. Thus, \(f[i][j] += f[i - 1][j] \times (j - k)\), where \(j \geq k\).

Therefore, we have the transition equation:

\[ f[i][j] = \begin{cases} 1 & i = 0, j = 0 \\ f[i - 1][j - 1] \times (n - j + 1) + f[i - 1][j] \times (j - k) & i \geq 1, j \geq 1 \end{cases} \]

The final answer is \(f[\textit{goal}][n]\).

The time complexity is \(O(\textit{goal} n)\), and the space complexity is \(O(\textit{goal} n)\), where \(\textit{goal}\) and \(n\) are the parameters given in the problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
        mod = 10**9 + 7
        f = [[0] * (n + 1) for _ in range(goal + 1)]
        f[0][0] = 1
        for i in range(1, goal + 1):
            for j in range(1, n + 1):
                f[i][j] = f[i - 1][j - 1] * (n - j + 1)
                if j > k:
                    f[i][j] += f[i - 1][j] * (j - k)
                f[i][j] %= mod
        return f[goal][n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int numMusicPlaylists(int n, int goal, int k) {
        final int mod = (int) 1e9 + 7;
        long[][] f = new long[goal + 1][n + 1];
        f[0][0] = 1;
        for (int i = 1; i <= goal; ++i) {
            for (int j = 1; j <= n; ++j) {
                f[i][j] = f[i - 1][j - 1] * (n - j + 1);
                if (j > k) {
                    f[i][j] += f[i - 1][j] * (j - k);
                }
                f[i][j] %= mod;
            }
        }
        return (int) f[goal][n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numMusicPlaylists(int n, int goal, int k) {
        const int mod = 1e9 + 7;
        long long f[goal + 1][n + 1];
        memset(f, 0, sizeof(f));
        f[0][0] = 1;
        for (int i = 1; i <= goal; ++i) {
            for (int j = 1; j <= n; ++j) {
                f[i][j] = f[i - 1][j - 1] * (n - j + 1);
                if (j > k) {
                    f[i][j] += f[i - 1][j] * (j - k);
                }
                f[i][j] %= mod;
            }
        }
        return f[goal][n];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func numMusicPlaylists(n int, goal int, k int) int {
    const mod = 1e9 + 7
    f := make([][]int, goal+1)
    for i := range f {
        f[i] = make([]int, n+1)
    }
    f[0][0] = 1
    for i := 1; i <= goal; i++ {
        for j := 1; j <= n; j++ {
            f[i][j] = f[i-1][j-1] * (n - j + 1)
            if j > k {
                f[i][j] += f[i-1][j] * (j - k)
            }
            f[i][j] %= mod
        }
    }
    return f[goal][n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function numMusicPlaylists(n: number, goal: number, k: number): number {
    const mod = 1e9 + 7;
    const f = new Array(goal + 1).fill(0).map(() => new Array(n + 1).fill(0));
    f[0][0] = 1;
    for (let i = 1; i <= goal; ++i) {
        for (let j = 1; j <= n; ++j) {
            f[i][j] = f[i - 1][j - 1] * (n - j + 1);
            if (j > k) {
                f[i][j] += f[i - 1][j] * (j - k);
            }
            f[i][j] %= mod;
        }
    }
    return f[goal][n];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
impl Solution {
    #[allow(dead_code)]
    pub fn num_music_playlists(n: i32, goal: i32, k: i32) -> i32 {
        let mut dp: Vec<Vec<i64>> = vec![vec![0; n as usize + 1]; goal as usize + 1];

        // Initialize the dp vector
        dp[0][0] = 1;

        // Begin the dp process
        for i in 1..=goal as usize {
            for j in 1..=n as usize {
                // Choose the song that has not been chosen before
                // We have n - (j - 1) songs to choose
                dp[i][j] += dp[i - 1][j - 1] * ((n - ((j as i32) - 1)) as i64);

                // Choose the song that has been chosen before
                // We have j - k songs to choose if j > k
                if (j as i32) > k {
                    dp[i][j] += dp[i - 1][j] * (((j as i32) - k) as i64);
                }

                // Update dp[i][j]
                dp[i][j] %= ((1e9 as i32) + 7) as i64;
            }
        }

        dp[goal as usize][n as usize] as i32
    }
}

Solution 2: Dynamic Programming (Space Optimization)

Thinking

Layer \(i\) depends only on \(f[i-1][j-1]\) and \(f[i-1][j]\), so the table rolls into one dimension and extra space becomes \(O(n)\).

We notice that \(f[i][j]\) is only related to \(f[i - 1][j - 1]\) and \(f[i - 1][j]\). Therefore, we can use a rolling array to optimize the space complexity, reducing the space complexity to \(O(n)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
        mod = 10**9 + 7
        f = [0] * (goal + 1)
        f[0] = 1
        for i in range(1, goal + 1):
            g = [0] * (goal + 1)
            for j in range(1, n + 1):
                g[j] = f[j - 1] * (n - j + 1)
                if j > k:
                    g[j] += f[j] * (j - k)
                g[j] %= mod
            f = g
        return f[n]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int numMusicPlaylists(int n, int goal, int k) {
        final int mod = (int) 1e9 + 7;
        long[] f = new long[n + 1];
        f[0] = 1;
        for (int i = 1; i <= goal; ++i) {
            long[] g = new long[n + 1];
            for (int j = 1; j <= n; ++j) {
                g[j] = f[j - 1] * (n - j + 1);
                if (j > k) {
                    g[j] += f[j] * (j - k);
                }
                g[j] %= mod;
            }
            f = g;
        }
        return (int) f[n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int numMusicPlaylists(int n, int goal, int k) {
        const int mod = 1e9 + 7;
        vector<long long> f(n + 1);
        f[0] = 1;
        for (int i = 1; i <= goal; ++i) {
            vector<long long> g(n + 1);
            for (int j = 1; j <= n; ++j) {
                g[j] = f[j - 1] * (n - j + 1);
                if (j > k) {
                    g[j] += f[j] * (j - k);
                }
                g[j] %= mod;
            }
            f = move(g);
        }
        return f[n];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func numMusicPlaylists(n int, goal int, k int) int {
    const mod = 1e9 + 7
    f := make([]int, goal+1)
    f[0] = 1
    for i := 1; i <= goal; i++ {
        g := make([]int, goal+1)
        for j := 1; j <= n; j++ {
            g[j] = f[j-1] * (n - j + 1)
            if j > k {
                g[j] += f[j] * (j - k)
            }
            g[j] %= mod
        }
        f = g
    }
    return f[n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function numMusicPlaylists(n: number, goal: number, k: number): number {
    const mod = 1e9 + 7;
    let f = new Array(goal + 1).fill(0);
    f[0] = 1;
    for (let i = 1; i <= goal; ++i) {
        const g = new Array(goal + 1).fill(0);
        for (let j = 1; j <= n; ++j) {
            g[j] = f[j - 1] * (n - j + 1);
            if (j > k) {
                g[j] += f[j] * (j - k);
            }
            g[j] %= mod;
        }
        f = g;
    }
    return f[n];
}

Comments