aboutsummaryrefslogtreecommitdiff
path: root/other/num_music_playlists.cpp
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
committerJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
commit7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch)
treeeb7a24ee2067f92245c57bb118e85a1baf15df50 /other/num_music_playlists.cpp
parent5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff)
downloadleetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz
leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip
chore: move cpp and rust code to directory
Diffstat (limited to 'other/num_music_playlists.cpp')
-rw-r--r--other/num_music_playlists.cpp40
1 files changed, 40 insertions, 0 deletions
diff --git a/other/num_music_playlists.cpp b/other/num_music_playlists.cpp
new file mode 100644
index 0000000..78cad3c
--- /dev/null
+++ b/other/num_music_playlists.cpp
@@ -0,0 +1,40 @@
+// 920. Number of Music Playlists
+#include "leetcode.h"
+
+/*
+ * 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, k', return the number of possible playlists that you can
+ * create. since the answer can be very large, return it modulo 10^9+7
+ */
+
+class Solution {
+ const int mod = 1e9 + 7;
+ long long solve(int n, int goal, int k, vvd & dp) {
+ if (!n && !goal)
+ return 1;
+ if (!n || !goal)
+ return 0;
+ if (dp[n][goal] != -1)
+ return dp[n][goal];
+ long long pick = solve(n - 1, goal - 1, k, dp) * n;
+ long long skip = solve(n, goal - 1, k, dp) * max(n - k, 0);
+ return dp[n][goal] = (pick + skip) % mod;
+ }
+
+public:
+ int numMusicPlaylists(int n, int goal, int k) {
+ vvd dp(n + 1, vector<int>(goal + 1, -1));
+ return solve(n, goal, k, dp);
+ }
+};
+
+int main() {
+ Solution obj;
+ printf("%d\n", obj.numMusicPlaylists(3, 3, 1)); // expect: 6
+ printf("%d\n", obj.numMusicPlaylists(2, 3, 0)); // expect: 6
+ printf("%d\n", obj.numMusicPlaylists(2, 3, 1)); // expect: 2
+}