In this guide, you will get 920. Number of Music Playlists LeetCode Solution with the best time and space complexity. The solution to Number of Music Playlists problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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].
920. Number of Music Playlists LeetCode Solution in C++
class Solution {
public:
int numMusicPlaylists(int n, int goal, int k) {
vector<vector<long>> mem(goal + 1, vector<long>(n + 1, -1));
return numMusicPlaylists(n, k, goal, n, mem);
}
private:
static constexpr int kMod = 1'000'000'007;
// Returns the number of playlists with i songs and j different songs.
long numMusicPlaylists(int n, int k, int i, int j,
vector<vector<long>>& mem) {
if (i == 0)
return j == 0;
if (j == 0)
return 0;
if (mem[i][j] >= 0)
return mem[i][j];
// The last song is new.
mem[i][j] = numMusicPlaylists(n, k, i - 1, j - 1, mem) * (n - (j - 1));
// The last song is old.
mem[i][j] += numMusicPlaylists(n, k, i - 1, j, mem) * max(0, j - k);
return mem[i][j] %= kMod;
}
}; /* code provided by PROGIEZ */
920. Number of Music Playlists LeetCode Solution in Java
class Solution {
public int numMusicPlaylists(int n, int goal, int k) {
long[][] mem = new long[goal + 1][n + 1];
Arrays.stream(mem).forEach(A -> Arrays.fill(A, -1));
return (int) numMusicPlaylists(n, k, goal, n, mem);
}
private static final int kMod = 1_000_000_007;
// Returns the number of playlists with i songs and j different songs.
private long numMusicPlaylists(int n, int k, int i, int j, long[][] mem) {
if (i == 0)
return j == 0 ? 1 : 0;
if (j == 0)
return 0;
if (mem[i][j] >= 0)
return mem[i][j];
// The last song is new.
mem[i][j] = numMusicPlaylists(n, k, i - 1, j - 1, mem) * (n - (j - 1));
// The last song is old.
mem[i][j] += numMusicPlaylists(n, k, i - 1, j, mem) * Math.max(0, j - k);
return mem[i][j] %= kMod;
}
} // code provided by PROGIEZ
920. Number of Music Playlists LeetCode Solution in Python
class Solution {
public:
int numMusicPlaylists(int n, int goal, int k) {
constexpr int kMod = 1'000'000'007;
// dp[i][j] := the number of playlists with i songs and j different songs
vector<vector<long>> dp(goal + 1, vector<long>(n + 1));
dp[0][0] = 1;
for (int i = 1; i <= goal; ++i)
for (int j = 1; j <= n; ++j) {
dp[i][j] += dp[i - 1][j - 1] * (n - (j - 1)); // The last song is new.
dp[i][j] += dp[i - 1][j] * max(0, j - k); // The last song is old.
dp[i][j] %= kMod;
}
return dp[goal][n];
}
}; # code by PROGIEZ
