You are given an array of positive integers nums and a positive integer k.
A permutation of nums is said to form a divisible concatenation if, when you concatenatethe decimal representations of the numbers in the order specified by the permutation, the resulting number is divisible byk.
Return the lexicographically smallest permutation (when considered as a list of integers) that forms a divisible concatenation. If no such permutation exists, return an empty list.
The problem asks for the lexicographically smallest permutation of nums such that the concatenation of the numbers is divisible by k. Since nums.length is at most 13, we can use bitmask DP to try all permutations efficiently. We keep track of which numbers are used and the current remainder modulo k.
classSolution {
funsmallestDivisiblePermutation(nums: IntArray, k: Int): List<Int> {
val n = nums.size
val lens = IntArray(n) { nums[it].toString().length }
val mods = IntArray(n) { nums[it] % k }
val memo = mutableMapOf<Pair<Int, Int>, List<Int>?>()
fundfs(mask: Int, rem: Int): List<Int>? {
if (mask == (1 shl n) - 1) returnif (rem ==0) listOf() elsenullval key = mask to rem
if (key in memo) return memo[key]
var ans: List<Int>? = nullfor (i in0 until n) {
if (mask and (1 shl i) ==0) {
val newRem = ((rem * Math.pow(10.0, lens[i].toDouble()) % k + mods[i]) % k).toInt()
val res = dfs(mask or (1 shl i), newRem)
if (res !=null) {
val cand = listOf(nums[i]) + res
if (ans ==null|| cand < ans) ans = cand
}
}
}
memo[key] = ans
return ans
}
return dfs(0, 0) ?: emptyList()
}
}
classSolution:
defsmallestDivisiblePermutation(self, nums: list[int], k: int) -> list[int]:
from functools import lru_cache
n = len(nums)
lens = [len(str(x)) for x in nums]
mods = [x % k for x in nums]
pow10 = [1]
for _ in range(6): pow10.append(pow10[-1]*10% k)
@lru_cache(None)
defdp(mask: int, rem: int) -> tuple:
if mask == (1<< n) -1:
return () if rem ==0elseNone ans =Nonefor i in range(n):
ifnot (mask & (1<< i)):
new_rem = (rem * pow(10, lens[i], k) + mods[i]) % k
res = dp(mask | (1<< i), new_rem)
if res isnotNone:
cand = (nums[i],) + res
if ans isNoneor cand < ans:
ans = cand
return ans
res = dp(0, 0)
return list(res) if res isnotNoneelse []
⏰ Time complexity: O(n! * n^2), where n is the length of nums. We try all n! permutations, and for each state, we may do up to n work to compare and build permutations. The DP/memoization table has O(n * 2^n * k) entries, but the dominant cost is the number of permutations.
🧺 Space complexity: O(n * 2^n * k * n), for the DP/memoization table, where each entry may store a permutation of up to n elements.