Problem

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 concatenate the decimal representations of the numbers in the order specified by the permutation, the resulting number is divisible by k.

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.

Examples

Example 1

1
2
Input: nums = [3,12,45], k = 5
Output: [3,12,45]

Explanation:

Permutation Concatenated Value Divisible by 5
[3, 12, 45] 31245 Yes
[3, 45, 12] 34512 No
[12, 3, 45] 12345 Yes
[12, 45, 3] 12453 No
[45, 3, 12] 45312 No
[45, 12, 3] 45123 No

The lexicographically smallest permutation that forms a divisible concatenation is [3,12,45].

Example 2

1
2
Input: nums = [10,5], k = 10
Output: [5,10]

Explanation:

Permutation Concatenated Value Divisible by 10
[5, 10] 510 Yes
[10, 5] 105 No

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

Example 3

1
2
3
4
5
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

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

Code

 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
29
30
31
32
33
34
35
class Solution {
public:
    vector<int> smallestDivisiblePermutation(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> lens(n), mods(n);
        for (int i = 0; i < n; ++i) {
            lens[i] = to_string(nums[i]).size();
            mods[i] = nums[i] % k;
        }
        vector<vector<vector<int>>> dp(1 << n, vector<vector<int>>(k));
        vector<vector<bool>> vis(1 << n, vector<bool>(k, false));
        function<vector<int>(int, int)> dfs = [&](int mask, int rem) -> vector<int> {
            if (mask == (1 << n) - 1) return rem == 0 ? vector<int>{} : vector<int>{-1};
            if (vis[mask][rem]) return dp[mask][rem];
            vis[mask][rem] = true;
            vector<int> ans;
            for (int i = 0; i < n; ++i) {
                if (!(mask & (1 << i))) {
                    int new_rem = (rem * (int)pow(10, lens[i]) % k + mods[i]) % k;
                    auto res = dfs(mask | (1 << i), new_rem);
                    if (!res.empty() && res[0] != -1) {
                        vector<int> cand = {nums[i]};
                        cand.insert(cand.end(), res.begin(), res.end());
                        if (ans.empty() || cand < ans) ans = cand;
                    }
                }
            }
            if (ans.empty()) ans = {-1};
            return dp[mask][rem] = ans;
        };
        auto res = dfs(0, 0);
        if (res.empty() || res[0] == -1) return {};
        return res;
    }
};
 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
func SmallestDivisiblePermutation(nums []int, k int) []int {
    n := len(nums)
    lens := make([]int, n)
    mods := make([]int, n)
    for i, v := range nums {
        lens[i] = len(strconv.Itoa(v))
        mods[i] = v % k
    }
    pow10 := make([]int, 20)
    pow10[0] = 1
    for i := 1; i < 20; i++ {
        pow10[i] = pow10[i-1] * 10 % k
    }
    type key struct{mask, rem int}
    memo := map[key][]int{}
    var dfs func(mask, rem int) []int
    dfs = func(mask, rem int) []int {
        if mask == (1<<n)-1 {
            if rem == 0 { return []int{} }
            return nil
        }
        if v, ok := memo[key{mask, rem}]; ok { return v }
        var ans []int
        for i := 0; i < n; i++ {
            if mask&(1<<i) == 0 {
                newRem := (rem*pow10[lens[i]]%k + mods[i]) % k
                res := dfs(mask|(1<<i), newRem)
                if res != nil {
                    cand := append([]int{nums[i]}, res...)
                    if ans == nil || less(cand, ans) { ans = cand }
                }
            }
        }
        memo[key{mask, rem}] = ans
        return ans
    }
    less := func(a, b []int) bool {
        for i := range a {
            if i >= len(b) || a[i] < b[i] { return true }
            if a[i] > b[i] { return false }
        }
        return len(a) < len(b)
    }
    res := dfs(0, 0)
    return res
}
 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
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public List<Integer> smallestDivisiblePermutation(int[] nums, int k) {
        int n = nums.length;
        int[] lens = new int[n], mods = new int[n];
        for (int i = 0; i < n; ++i) {
            lens[i] = Integer.toString(nums[i]).length();
            mods[i] = nums[i] % k;
        }
        Map<String, List<Integer>> memo = new HashMap<>();
        List<Integer> dfs(int mask, int rem) {
            if (mask == (1 << n) - 1) return rem == 0 ? new ArrayList<>() : null;
            String key = mask + "," + rem;
            if (memo.containsKey(key)) return memo.get(key);
            List<Integer> ans = null;
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) == 0) {
                    int newRem = (int)((rem * Math.pow(10, lens[i]) % k + mods[i]) % k);
                    List<Integer> res = dfs(mask | (1 << i), newRem);
                    if (res != null) {
                        List<Integer> cand = new ArrayList<>();
                        cand.add(nums[i]);
                        cand.addAll(res);
                        if (ans == null || compare(cand, ans) < 0) ans = cand;
                    }
                }
            }
            memo.put(key, ans);
            return ans;
        }
        List<Integer> res = dfs(0, 0);
        return res == null ? new ArrayList<>() : res;
    }
    int compare(List<Integer> a, List<Integer> b) {
        for (int i = 0; i < a.size() && i < b.size(); ++i) {
            if (!a.get(i).equals(b.get(i))) return a.get(i) - b.get(i);
        }
        return a.size() - b.size();
    }
}
 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
class Solution {
    fun smallestDivisiblePermutation(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>?>()
        fun dfs(mask: Int, rem: Int): List<Int>? {
            if (mask == (1 shl n) - 1) return if (rem == 0) listOf() else null
            val key = mask to rem
            if (key in memo) return memo[key]
            var ans: List<Int>? = null
            for (i in 0 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()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def smallestDivisiblePermutation(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)
        def dp(mask: int, rem: int) -> tuple:
            if mask == (1 << n) - 1:
                return () if rem == 0 else None
            ans = None
            for i in range(n):
                if not (mask & (1 << i)):
                    new_rem = (rem * pow(10, lens[i], k) + mods[i]) % k
                    res = dp(mask | (1 << i), new_rem)
                    if res is not None:
                        cand = (nums[i],) + res
                        if ans is None or cand < ans:
                            ans = cand
            return ans
        res = dp(0, 0)
        return list(res) if res is not None else []
 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
29
30
31
32
33
impl Solution {
    pub fn smallest_divisible_permutation(nums: Vec<i32>, k: i32) -> Vec<i32> {
        use std::collections::HashMap;
        let n = nums.len();
        let lens: Vec<usize> = nums.iter().map(|x| x.to_string().len()).collect();
        let mods: Vec<i32> = nums.iter().map(|&x| x % k).collect();
        let mut memo = HashMap::new();
        fn dfs(mask: usize, rem: i32, n: usize, k: i32, nums: &Vec<i32>, lens: &Vec<usize>, mods: &Vec<i32>, memo: &mut HashMap<(usize, i32), Option<Vec<i32>>>) -> Option<Vec<i32>> {
            if mask == (1 << n) - 1 {
                return if rem == 0 { Some(vec![]) } else { None };
            }
            if let Some(ans) = memo.get(&(mask, rem)) { return ans.clone(); }
            let mut best: Option<Vec<i32>> = None;
            for i in 0..n {
                if mask & (1 << i) == 0 {
                    let mut pow10 = 1;
                    for _ in 0..lens[i] { pow10 = pow10 * 10 % k; }
                    let new_rem = (rem * pow10 + mods[i]) % k;
                    if let Some(mut res) = dfs(mask | (1 << i), new_rem, n, k, nums, lens, mods, memo) {
                        let mut cand = vec![nums[i]];
                        cand.append(&mut res);
                        if best.is_none() || cand < best.as_ref().unwrap().as_slice() {
                            best = Some(cand);
                        }
                    }
                }
            }
            memo.insert((mask, rem), best.clone());
            best
        }
        dfs(0, 0, n, k, &nums, &lens, &mods, &mut memo).unwrap_or(vec![])
    }
}
 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
class Solution {
    smallestDivisiblePermutation(nums: number[], k: number): number[] {
        const n = nums.length;
        const lens = nums.map(x => x.toString().length);
        const mods = nums.map(x => x % k);
        const memo = new Map<string, number[] | null>();
        function dfs(mask: number, rem: number): number[] | null {
            if (mask === (1 << n) - 1) return rem === 0 ? [] : null;
            const key = mask + ',' + rem;
            if (memo.has(key)) return memo.get(key)!;
            let ans: number[] | null = null;
            for (let i = 0; i < n; ++i) {
                if ((mask & (1 << i)) === 0) {
                    const newRem = (rem * Math.pow(10, lens[i]) % k + mods[i]) % k;
                    const res = dfs(mask | (1 << i), newRem);
                    if (res !== null) {
                        const cand = [nums[i], ...res];
                        if (ans === null || cand.join(',') < ans.join(',')) ans = cand;
                    }
                }
            }
            memo.set(key, ans);
            return ans;
        }
        const res = dfs(0, 0);
        return res === null ? [] : res;
    }
}

Complexity

  • ⏰ 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.