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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5

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:

1
2
3
4
5

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

Solution

The goal is to find the number of distinct playlists of length goal that can be created using n different songs, with the constraint that the same song cannot appear in consecutive positions in the playlist, and there should be at least k songs between any two occurrences of the same song.

Method 1 - Recursion

We want to count the number of playlists of length goal using n different songs, where:

  • Every song is played at least once.
  • A song can only be repeated if at least k other songs have been played since its last occurrence.

Approach

  1. Base cases: - If there are no songs left (n == 0) and the playlist length is also zero(goal == 0),w e have found a valid playlist, so return 1. - If there are no songs left (n == 0) but the playlist length is still greater than zero (goal > 0), or vice versa, it is not possible to create a valid playlist, so return 0.
  2. Recursive steps:
    • Pick a new song: Choose a song not yet played. There are n choices, and the rest of the playlist is formed by solve(n-1, goal-1, k). So, add n * solve(n-1, goal-1, k).
    • Repeat a song: Choose a song already played, but only if at least k other songs have been played since. There are max(n-k, 0) choices, and the rest of the playlist is formed by solve(n, goal-1, k). So, add max(n-k, 0) * solve(n, goal-1, k).
  3. Return the sum of both options.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
	int numMusicPlaylists(int n, int goal, int k) {
		int mod = 1e9 + 7;
		return (int)dfs(n, goal, k, mod);
	}
	long dfs(int n, int goal, int k, int mod) {
		if (n == 0 && goal == 0) return 1;
		if (n == 0 || goal == 0) return 0;
		long pick = dfs(n - 1, goal - 1, k, mod) * n % mod;
		long repeat = dfs(n, goal - 1, k, mod) * max(n - k, 0) % mod;
		return (pick + repeat) % mod;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func numMusicPlaylists(n int, goal int, k int) int {
	mod := int(1e9 + 7)
	var dfs func(int, int) int
	dfs = func(n, goal int) int {
		if n == 0 && goal == 0 {
			return 1
		}
		if n == 0 || goal == 0 {
			return 0
		}
		pick := dfs(n-1, goal-1) * n % mod
		repeat := dfs(n, goal-1) * max(n-k, 0) % mod
		return (pick + repeat) % mod
	}
	return dfs(n, goal)
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	private static final int MOD = (int)1e9 + 7;
	public int numMusicPlaylists(int n, int goal, int k) {
		return (int)dfs(n, goal, k);
	}
	private long dfs(int n, int goal, int k) {
		if (n == 0 && goal == 0) return 1;
		if (n == 0 || goal == 0) return 0;
		long pick = dfs(n - 1, goal - 1, k) * n % MOD;
		long repeat = dfs(n, goal - 1, k) * Math.max(n - k, 0) % MOD;
		return (pick + repeat) % MOD;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	fun numMusicPlaylists(n: Int, goal: Int, k: Int): Int {
		val mod = 1_000_000_007
		fun dfs(n: Int, goal: Int): Long {
			if (n == 0 && goal == 0) return 1L
			if (n == 0 || goal == 0) return 0L
			val pick = dfs(n - 1, goal - 1) * n % mod
			val repeat = dfs(n, goal - 1) * maxOf(n - k, 0) % mod
			return (pick + repeat) % mod
		}
		return dfs(n, goal).toInt()
	}
}
 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
		def dfs(n: int, goal: int) -> int:
			if n == 0 and goal == 0:
				return 1
			if n == 0 or goal == 0:
				return 0
			pick = dfs(n - 1, goal - 1) * n % mod
			repeat = dfs(n, goal - 1) * max(n - k, 0) % mod
			return (pick + repeat) % mod
		return dfs(n, goal)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

impl Solution {
	pub fn num_music_playlists(n: i32, goal: i32, k: i32) -> i32 {
		fn dfs(n: i32, goal: i32, k: i32, modv: i32) -> i64 {
			if n == 0 && goal == 0 { return 1; }
			if n == 0 || goal == 0 { return 0; }
			let pick = dfs(n - 1, goal - 1, k, modv) * n as i64 % modv as i64;
			let repeat = dfs(n, goal - 1, k, modv) * ((n - k).max(0) as i64) % modv as i64;
			(pick + repeat) % modv as i64
		}
		dfs(n, goal, k, 1_000_000_007) as i32
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
	numMusicPlaylists(n: number, goal: number, k: number): number {
		const mod = 1e9 + 7;
		function dfs(n: number, goal: number): number {
			if (n === 0 && goal === 0) return 1;
			if (n === 0 || goal === 0) return 0;
			const pick = dfs(n - 1, goal - 1) * n % mod;
			const repeat = dfs(n, goal - 1) * Math.max(n - k, 0) % mod;
			return (pick + repeat) % mod;
		}
		return dfs(n, goal);
	}
}

Complexity

  • ⏰ Time complexity: O(2^goal), since each call can branch into two subproblems and there is no memoization.
  • 🧺 Space complexity: O(goal), due to recursion stack.

Method 2 - TD D with Memo

We can just add dp[n+1][goal+1] cache: If the value of dp[n][goal] is already calculated (not equal to -1), return it. This is the memoization step to avoid redundant calculations.

Also, at the end of recursion, store it in dp[n][goal] for future use.

Code

 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) {
		int mod = 1e9 + 7;
		vector<vector<long>> memo(n + 1, vector<long>(goal + 1, -1));
		return (int)dfs(n, goal, k, mod, memo);
	}
	long dfs(int n, int goal, int k, int mod, vector<vector<long>>& memo) {
		if (n == 0 && goal == 0) return 1;
		if (n == 0 || goal == 0) return 0;
		if (memo[n][goal] != -1) return memo[n][goal];
		long pick = dfs(n - 1, goal - 1, k, mod, memo) * n % mod;
		long repeat = dfs(n, goal - 1, k, mod, memo) * max(n - k, 0) % mod;
		memo[n][goal] = (pick + repeat) % mod;
		return memo[n][goal];
	}
};
 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

func numMusicPlaylists(n int, goal int, k int) int {
	mod := int(1e9 + 7)
	memo := make(map[[2]int]int)
	var dfs func(int, int) int
	dfs = func(n, goal int) int {
		if n == 0 && goal == 0 {
			return 1
		}
		if n == 0 || goal == 0 {
			return 0
		}
		key := [2]int{n, goal}
		if v, ok := memo[key]; ok {
			return v
		}
		pick := dfs(n-1, goal-1) * n % mod
		repeat := dfs(n, goal-1) * max(n-k, 0) % mod
		memo[key] = (pick + repeat) % mod
		return memo[key]
	}
	return dfs(n, goal)
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
	private static final int MOD = (int)1e9 + 7;
	public int numMusicPlaylists(int n, int goal, int k) {
		Long[][] memo = new Long[n + 1][goal + 1];
		return (int)dfs(n, goal, k, memo);
	}
	private long dfs(int n, int goal, int k, Long[][] memo) {
		if (n == 0 && goal == 0) return 1;
		if (n == 0 || goal == 0) return 0;
		if (memo[n][goal] != null) return memo[n][goal];
		long pick = dfs(n - 1, goal - 1, k, memo) * n % MOD;
		long repeat = dfs(n, goal - 1, k, memo) * Math.max(n - k, 0) % MOD;
		memo[n][goal] = (pick + repeat) % MOD;
		return memo[n][goal];
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
	fun numMusicPlaylists(n: Int, goal: Int, k: Int): Int {
		val mod = 1_000_000_007
		val memo = Array(n + 1) { LongArray(goal + 1) { -1L } }
		fun dfs(n: Int, goal: Int): Long {
			if (n == 0 && goal == 0) return 1L
			if (n == 0 || goal == 0) return 0L
			if (memo[n][goal] != -1L) return memo[n][goal]
			val pick = dfs(n - 1, goal - 1) * n % mod
			val repeat = dfs(n, goal - 1) * maxOf(n - k, 0) % mod
			memo[n][goal] = (pick + repeat) % mod
			return memo[n][goal]
		}
		return dfs(n, goal).toInt()
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
	def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
		mod = 10**9 + 7
		memo = {}
		def dfs(n: int, goal: int) -> int:
			if n == 0 and goal == 0:
				return 1
			if n == 0 or goal == 0:
				return 0
			key = (n, goal)
			if key in memo:
				return memo[key]
			pick = dfs(n - 1, goal - 1) * n % mod
			repeat = dfs(n, goal - 1) * max(n - k, 0) % mod
			memo[key] = (pick + repeat) % mod
			return memo[key]
		return dfs(n, goal)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
	pub fn num_music_playlists(n: i32, goal: i32, k: i32) -> i32 {
		fn dfs(n: i32, goal: i32, k: i32, modv: i32, memo: &mut Vec<Vec<i64>>) -> i64 {
			if n == 0 && goal == 0 { return 1; }
			if n == 0 || goal == 0 { return 0; }
			if memo[n as usize][goal as usize] != -1 { return memo[n as usize][goal as usize]; }
			let pick = dfs(n - 1, goal - 1, k, modv, memo) * n as i64 % modv as i64;
			let repeat = dfs(n, goal - 1, k, modv, memo) * ((n - k).max(0) as i64) % modv as i64;
			memo[n as usize][goal as usize] = (pick + repeat) % modv as i64;
			memo[n as usize][goal as usize]
		}
		let mut memo = vec![vec![-1; (goal + 1) as usize]; (n + 1) as usize];
		dfs(n, goal, k, 1_000_000_007, &mut memo) as i32
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
	numMusicPlaylists(n: number, goal: number, k: number): number {
		const mod = 1e9 + 7;
		const memo: Record<string, number> = {};
		function dfs(n: number, goal: number): number {
			if (n === 0 && goal === 0) return 1;
			if (n === 0 || goal === 0) return 0;
			const key = `${n},${goal}`;
			if (memo[key] !== undefined) return memo[key];
			const pick = dfs(n - 1, goal - 1) * n % mod;
			const repeat = dfs(n, goal - 1) * Math.max(n - k, 0) % mod;
			memo[key] = (pick + repeat) % mod;
			return memo[key];
		}
		return dfs(n, goal);
	}
}

Complexity

  • ⏰ Time complexity: O(n*goal), since each subproblem (n, goal) is solved only once and stored in the memoization table.
  • 🧺 Space complexity: O(n*goal), for the memoization table and recursion stack.