# 06.08.2023 [920. Number of Music Playlists]

Playlists number playing `n` songs `goal` times, repeating each once in a `k` times

06.08.2023

920. Number of Music Playlists hard
blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/300

Problem TLDR

Playlists number playing n songs goal times, repeating each once in a k times

Intuition

We can search through the problem space, taking each new song with the given rules: song can be repeated only after another k song got played. When we have the goal songs, check if all distinct songs are played.

We can cache the solution by curr and used map, but that will give TLE.

The hard trick here is that the result only depends on how many distinct songs are played.

Approach

Use DFS and memo.

Complexity

• Time complexity:
  O(n^2)

• Space complexity:
  O(n^2)

Code

    fun numMusicPlaylists(n: Int, goal: Int, k: Int): Int {
        val cache = mutableMapOf<Pair<Int, Int>, Long>()
        fun dfs(curr: Int, used: Map<Int, Int>): Long = cache.getOrPut(curr to used.size) {
          if (curr > goal) { 
            if ((1..n).all { used.contains(it) }) 1L else 0L 
          } else (1..n).asSequence().map { i -> 
              if (curr <= used[i] ?: 0) 0L else
                dfs(curr + 1, used.toMutableMap().apply { this[i] = curr + k })
            }.sum()!! % 1_000_000_007L
        }
        return dfs(1, mapOf()).toInt()
    }