Concatenated Divisibility
HardUpdated: Jul 26, 2025
Practice on:
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
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
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
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 <= 131 <= nums[i] <= 10^51 <= 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
C++
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;
}
};
Go
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
}
Java
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();
}
}
Kotlin
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()
}
}
Python
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 []
Rust
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![])
}
}
TypeScript
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.