[5, 10]510Yes[10, 5]105No

The lexicographically smallest permutation that forms a divisible concatenation is [5,10].

Example 3

Input: nums = [1,2,3], k = 5
Output: []
Explanation:
Since no permutation of `nums` forms a valid divisible concatenation, return
an empty list.

Constraints

1 <= nums.length <= 13
1 <= nums[i] <= 10^5
1 <= k <= 100

Solution

Method 1 – Bitmask Dynamic Programming

Intuition

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.

Approach

Precompute the length and modulo of each number in nums for fast concatenation calculations.
Use a DP table: dp[mask][rem] = the lex smallest permutation for the used mask and current remainder rem.
For each state, try adding each unused number, updating the mask and the new remainder after concatenation.
If a full permutation (all numbers used) has rem == 0, return the permutation.
If no such permutation exists, return an empty list.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    vector<int> smallestDivisiblePermutation(vector<int>& nums, int k) {\n        int n = nums.size();\n        vector<int> lens(n), mods(n);\n        for (int i = 0; i < n; ++i) {\n            lens[i] = to_string(nums[i]).size();\n            mods[i] = nums[i] % k;\n        }\n        vector<vector<vector<int>>> dp(1 << n, vector<vector<int>>(k));\n        vector<vector<bool>> vis(1 << n, vector<bool>(k, false));\n        function<vector<int>(int, int)> dfs = [&](int mask, int rem) -> vector<int> {\n            if (mask == (1 << n) - 1) return rem == 0 ? vector<int>{} : vector<int>{-1};\n            if (vis[mask][rem]) return dp[mask][rem];\n            vis[mask][rem] = true;\n            vector<int> ans;\n            for (int i = 0; i < n; ++i) {\n                if (!(mask & (1 << i))) {\n                    int new_rem = (rem * (int)pow(10, lens[i]) % k + mods[i]) % k;\n                    auto res = dfs(mask | (1 << i), new_rem);\n                    if (!res.empty() && res[0] != -1) {\n                        vector<int> cand = {nums[i]};\n                        cand.insert(cand.end(), res.begin(), res.end());\n                        if (ans.empty() || cand < ans) ans = cand;\n                    }\n                }\n            }\n            if (ans.empty()) ans = {-1};\n            return dp[mask][rem] = ans;\n        };\n        auto res = dfs(0, 0);\n        if (res.empty() || res[0] == -1) return {};\n        return res;\n    }\n};","lang":"cpp"},{"language":"Go","code":"func SmallestDivisiblePermutation(nums []int, k int) []int {\n    n := len(nums)\n    lens := make([]int, n)\n    mods := make([]int, n)\n    for i, v := range nums {\n        lens[i] = len(strconv.Itoa(v))\n        mods[i] = v % k\n    }\n    pow10 := make([]int, 20)\n    pow10[0] = 1\n    for i := 1; i < 20; i++ {\n        pow10[i] = pow10[i-1] * 10 % k\n    }\n    type key struct{mask, rem int}\n    memo := map[key][]int{}\n    var dfs func(mask, rem int) []int\n    dfs = func(mask, rem int) []int {\n        if mask == (1<<n)-1 {\n            if rem == 0 { return []int{} }\n            return nil\n        }\n        if v, ok := memo[key{mask, rem}]; ok { return v }\n        var ans []int\n        for i := 0; i < n; i++ {\n

Related Tags