LeetCode 3533 - Concatenated Divisibility
We are given an array nums containing up to 13 positive integers and an integer k. We may reorder the numbers in any permutation. After choosing an ordering, we concatenate the decimal representations of the numbers to form a single large integer.
Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Bit Manipulation, Bitmask
Solution
LeetCode 3533 - Concatenated Divisibility
Problem Understanding
We are given an array nums containing up to 13 positive integers and an integer k.
We may reorder the numbers in any permutation. After choosing an ordering, we concatenate the decimal representations of the numbers to form a single large integer. The task is to find a permutation whose concatenated value is divisible by k.
Among all valid permutations, we must return the lexicographically smallest permutation, where lexicographic comparison is performed on the list of integers themselves. If no valid permutation exists, we return an empty list.
For example, if:
nums = [3, 12, 45]
then the permutation:
[3, 12, 45]
produces:
31245
and since 31245 % 5 == 0, it is a valid answer.
The most important observation is that the concatenated number can become extremely large. With up to 13 numbers and each number containing up to 6 digits, the final concatenation may contain nearly 80 digits. Such values cannot be handled directly with standard integer arithmetic in many languages.
The constraints are:
1 <= n <= 13
1 <= nums[i] <= 100000
1 <= k <= 100
The small value of n suggests that solutions involving subsets, bitmasks, and dynamic programming over permutations may be feasible. Since 2^13 = 8192, a state space involving all subsets is manageable.
Several edge cases are important:
- No permutation may satisfy the divisibility condition.
- Multiple valid permutations may exist, requiring us to return the lexicographically smallest one.
- Values can have different digit lengths, which affects concatenation.
- Duplicate numbers may appear, and lexicographic ordering must still be respected.
- The concatenated value may be far larger than built-in integer limits, so direct construction is unsafe.
Approaches
Brute Force
The most direct approach is to generate every permutation of nums.
For each permutation:
- Concatenate the numbers.
- Compute the resulting value.
- Check whether it is divisible by
k. - Keep the lexicographically smallest valid permutation.
This approach is correct because it explicitly examines every possible ordering.
However, the number of permutations is:
n!
For n = 13:
13! = 6,227,020,800
which is completely infeasible.
Key Insight
When concatenating numbers, we only care about the remainder modulo k.
Suppose the current concatenated value has remainder:
r
and we append a number x with d digits.
The new value is:
r * 10^d + x
Therefore the new remainder becomes:
(r * 10^d + x) % k
This means we never need the full concatenated number. We only need its remainder modulo k.
Since:
- there are only
2^nsubsets, - there are only
kpossible remainders,
we can perform dynamic programming on:
(mask, remainder)
where:
maskindicates which numbers have already been used,remainderis the current concatenation remainder modulok.
After determining which states can eventually reach a valid solution, we greedily construct the lexicographically smallest permutation.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n! · n) | O(n) | Enumerates every permutation |
| Optimal DP + Bitmask | O(2^n · n · k) | O(2^n · k) | Uses subset DP on remainders |
Algorithm Walkthrough
1. Precompute digit lengths
For every number:
digits[i] = number of decimal digits in nums[i]
This tells us how many powers of ten are needed when appending that number.
2. Precompute powers of ten modulo k
For each distinct digit length:
pow10[d] = 10^d mod k
This allows remainder transitions in O(1).
3. Precompute each number modulo k
For every number:
valueMod[i] = nums[i] % k
Only the remainder is needed.
4. Define DP state
Let:
dp(mask, rem)
mean:
Is it possible to complete the permutation using the unused numbers so that the final concatenation becomes divisible by k?
The state is determined by:
- which numbers have already been used,
- the current remainder.
5. Base case
When all numbers have been used:
mask == (1<<n)-1
the concatenation is complete.
The state is successful only if:
rem == 0
6. Transition
For every unused index i:
newRem =
(rem * pow10[digits[i]] + valueMod[i]) % k
If:
dp(mask | (1<<i), newRem)
is true, then:
dp(mask, rem)
is also true.
7. Check existence
Evaluate:
dp(0, 0)
If it is false, return an empty list.
8. Construct lexicographically smallest answer
Sort indices by:
(nums[i], i)
At each position:
- Try candidate numbers in increasing order.
- Compute the resulting remainder.
- Check whether the corresponding DP state can still reach a solution.
- Choose the first candidate that works.
Because candidates are tested in lexicographic order, the first successful choice produces the lexicographically smallest valid permutation.
Why it works
The DP correctly determines whether a state can be extended into a complete valid permutation because every transition corresponds exactly to appending one unused number. The base case checks whether the final remainder is zero, which is precisely the divisibility requirement.
During reconstruction, candidates are considered in lexicographic order. Whenever the first feasible candidate is chosen, all smaller candidates have already been proven incapable of reaching a valid completion. Therefore the resulting sequence is the lexicographically smallest valid permutation.
Problem Understanding
We are given an array nums of length at most 13 and a positive integer k ≤ 100. We must consider every permutation of nums. For a fixed permutation, we form a single integer by concatenating the decimal representations of the numbers in order, and we ask whether this resulting integer is divisible by k.
The task is not merely to decide existence. We must return the lexicographically smallest permutation of the integers themselves (not their digits) that yields a concatenated number divisible by k. Lexicographic order is defined on the sequence of integers as a sequence comparison: compare element by element from left to right, and the first differing element determines order.
The constraints imply that brute force over all permutations, up to 13! ≈ 6.2 × 10^9, is infeasible. However, n ≤ 13 strongly suggests a bitmask dynamic programming solution over subsets. The modulus constraint k ≤ 100 further suggests that tracking remainder states is sufficient.
A naive implementation would fail because both permutation enumeration and full integer concatenation are too large. Instead, we exploit that divisibility depends only on the remainder modulo k, and concatenation can be modeled arithmetically.
Edge cases include a single element array, multiple identical remainders leading to no solution, and cases where no permutation yields remainder zero. Another subtle case is lexicographic minimality under multiple valid solutions, which requires careful ordering during reconstruction.
Approaches
A brute-force method enumerates all permutations of nums, constructs the concatenated integer as a string or big integer, and checks divisibility by k. This is correct but factorial in time and infeasible for n = 13.
The optimal approach uses bitmask dynamic programming. We define states by (mask, r), where mask indicates which elements are already used and r is the current remainder modulo k of the concatenated prefix. We precompute how each number transforms the remainder when appended. We then determine whether a full completion exists from a state and reconstruct the lexicographically smallest valid permutation greedily.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n! · n · d) | O(n) | Enumerate permutations and compute concatenation directly |
| Optimal DP (bitmask + mod) | O(2^n · n · k) | O(2^n · k) | State compression with remainder DP and reconstruction |
Here d is digit length overhead for concatenation simulation.
Algorithm Walkthrough
We formalize the concatenation process modulo k. Let each number a_i have digit length len_i. If current remainder is r, appending a_i yields:
$$r' = (r \cdot 10^{len_i} + a_i) \bmod k$$
We precompute pow10[i] = 10^{len_i} mod k and val[i] = a_i mod k.
Steps
- We compute for each index
ithe number of digitslen_i, the value modulok, andpow10[i] = 10^{len_i} mod k. This ensures that concatenation can be simulated in O(1). - We define a DP function
can(mask, r)which returns whether it is possible to use exactly the unused elements and eventually reach a full permutation whose final remainder is zero. - The base case is when
maskincludes all elements. In that case, the state is valid if and only ifr == 0. - For a general state
(mask, r), we try appending any unused elementi. The transition is to(mask ∪ {i}, r')using the modular update rule. If any transition leads to a solvable state, the current state is solvable. - We memoize
can(mask, r)to ensure each state is computed once. The total number of states is2^n · k. - To construct the lexicographically smallest valid permutation, we start from
(mask = 0, r = 0)and repeatedly choose the smallest indexi(by value, then index tie-break if needed) such that the transition leads to a solvable state. - We append that element, update
(mask, r), and continue until all elements are used.
Why it works
The DP defines a complete characterization of feasibility from any partial permutation prefix. The greedy reconstruction is valid because at each step we only choose transitions that preserve the existence of a full solution, and selecting the smallest valid element at each step preserves lexicographic minimality by definition of lexicographic order and the optimal substructure of the DP state space.
Python Solution
from typing import List
from functools import lru_cache
class Solution:
def concatenatedDivisibility(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
digits = [len(str(x)) for x in nums]
max_digits = max(digits)
pow10 = [1] * (max_digits + 1)
for d in range(1, max_digits + 1):
pow10[d] = (pow10[d - 1] * 10) % k
num_mod = [x % k for x in nums]
full_mask = (1 << n) - 1
@lru_cache(None)
def dp(mask: int, rem: int) -> bool:
if mask == full_mask:
return rem == 0
for i in range(n):
if (mask >> i) & 1:
continue
new_rem = (
rem * pow10[digits[i]] + num_mod[i]
) % k
if dp(mask | (1 << i), new_rem):
return True
return False
if not dp(0, 0):
return []
order = sorted(range(n), key=lambda i: (nums[i], i))
answer = []
mask = 0
rem = 0
for _ in range(n):
for idx in order:
if (mask >> idx) & 1:
continue
new_rem = (
rem * pow10[digits[idx]] + num_mod[idx]
) % k
if dp(mask | (1 << idx), new_rem):
answer.append(nums[idx])
mask |= 1 << idx
rem = new_rem
break
return answer
Implementation Explanation
The first section computes digit lengths and powers of ten modulo k. These values allow concatenation remainders to be updated without constructing large integers.
The memoized dp(mask, rem) function explores all unused numbers and determines whether a successful completion exists. Since every state is computed once, memoization eliminates exponential recomputation.
After confirming that a solution exists, reconstruction begins. Indices are sorted by their corresponding values so that smaller numbers are always considered first. For each position, the algorithm checks whether choosing a candidate still leaves a path to a valid final remainder. The first successful candidate is permanently selected.
This reconstruction phase converts the feasibility DP into the lexicographically smallest valid permutation.
# Precompute digit lengths and modulo contributions
lens = []
mod_vals = []
pow10 = []
for x in nums:
s = str(x)
lens.append(len(s))
mod_vals.append(x % k)
for l in lens:
p = 1
for _ in range(l):
p = (p * 10) % k
pow10.append(p)
full_mask = (1 << n) - 1
@lru_cache(None)
def can(mask: int, rem: int) -> bool:
if mask == full_mask:
return rem == 0
for i in range(n):
if not (mask & (1 << i)):
new_rem = (rem * pow10[i] + mod_vals[i]) % k
if can(mask | (1 << i), new_rem):
return True
return False
if not can(0, 0):
return []
result = []
mask = 0
rem = 0
# Greedy reconstruction
for _ in range(n):
for i in range(n):
if mask & (1 << i):
continue
new_rem = (rem * pow10[i] + mod_vals[i]) % k
if can(mask | (1 << i), new_rem):
result.append(nums[i])
mask |= (1 << i)
rem = new_rem
break
return result
### Code Explanation
We first preprocess each number into digit length and modular representation so that concatenation becomes a constant-time arithmetic update. The memoized function `can(mask, rem)` encodes the feasibility of completing a permutation from a partial state. It explores all unused elements and checks whether at least one leads to a valid terminal configuration.
After confirming feasibility from the empty state, we reconstruct the lexicographically smallest solution by trying candidates in increasing index order and selecting the first that preserves solvability. This greedy step is justified by the DP feasibility oracle.
## Go Solution
```go
func concatenatedDivisibility(nums []int, k int) []int {
n := len(nums)
digits := make([]int, n)
maxDigits := 0
for i, x := range nums {
d := len([]byte(string(rune(0))))
_ = d
v := x
cnt := 0
for v > 0 {
cnt++
v /= 10
}
if cnt == 0 {
cnt = 1
}
digits[i] = cnt
if cnt > maxDigits {
maxDigits = cnt
}
}
pow10 := make([]int, maxDigits+1)
pow10[0] = 1 % k
for i := 1; i <= maxDigits; i++ {
pow10[i] = (pow10[i-1] * 10) % k
}
numMod := make([]int, n)
for i := range nums {
numMod[i] = nums[i] % k
}
fullMask := (1 << n) - 1
memo := make(map[[2]int]bool)
seen := make(map[[2]int]bool)
var dp func(int, int) bool
dp = func(mask, rem int) bool {
package main
func concatenatedDivisibility(nums []int, k int) []int {
n := len(nums)
fullMask := (1 << n) - 1
lens := make([]int, n)
modVals := make([]int, n)
pow10 := make([]int, n)
for i, x := range nums {
modVals[i] = x % k
l := 0
for t := x; t > 0; t /= 10 {
l++
}
lens[i] = l
p := 1 % k
for j := 0; j < l; j++ {
p = (p * 10) % k
}
pow10[i] = p
}
memo := make(map[[2]int]bool)
var can func(mask, rem int) bool
can = func(mask, rem int) bool {
key := [2]int{mask, rem}
if v, ok := memo[key]; ok {
return v
}
if mask == fullMask {
return rem == 0
}
key := [2]int{mask, rem}
if seen[key] {
return memo[key]
}
seen[key] = true
for i := 0; i < n; i++ {
if (mask>>i)&1 == 1 {
continue
}
newRem := (rem*pow10[digits[i]] + numMod[i]) % k
if dp(mask|(1<<i), newRem) {
memo[key] = true
return true
for i := 0; i < n; i++ {
if mask&(1<<i) == 0 {
newRem := (rem*pow10[i] + modVals[i]) % k
if can(mask|(1<<i), newRem) {
memo[key] = true
return true
}
}
}
memo[key] = false
return false
}
if !dp(0, 0) {
return []int{}
}
order := make([]int, n)
for i := range order {
order[i] = i
}
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if nums[order[j]] < nums[order[i]] {
order[i], order[j] = order[j], order[i]
}
}
}
ans := make([]int, 0, n)
mask := 0
rem := 0
for len(ans) < n {
for _, idx := range order {
if (mask>>idx)&1 == 1 {
continue
}
newRem := (rem*pow10[digits[idx]] + numMod[idx]) % k
if dp(mask|(1<<idx), newRem) {
ans = append(ans, nums[idx])
mask |= 1 << idx
if !can(0, 0) {
return []int{}
}
res := make([]int, 0, n)
mask := 0
rem := 0
for len(res) < n {
for i := 0; i < n; i++ {
if mask&(1<<i) != 0 {
continue
}
newRem := (rem*pow10[i] + modVals[i]) % k
if can(mask|(1<<i), newRem) {
res = append(res, nums[i])
mask |= (1 << i)
rem = newRem
break
}
}
}
return ans
}
Go-Specific Notes
The overall logic is identical to the Python solution.
Memoization is implemented using maps keyed by (mask, remainder) pairs. Go does not provide built-in memoized recursion, so both a seen map and a memo map are used.
Because the largest possible concatenated value is enormous, the implementation never constructs it directly. All calculations remain modulo k, avoiding overflow concerns.
Worked Examples
Example 1
nums = [3,12,45]
k = 5
Digit lengths:
| Number | Digits |
|---|---|
| 3 | 1 |
| 12 | 2 |
| 45 | 2 |
Relevant remainders:
| Number | Mod 5 |
|---|---|
| 3 | 3 |
| 12 | 2 |
| 45 | 0 |
Reconstruction begins at:
| Mask | Remainder |
|---|---|
| 000 | 0 |
Try numbers in sorted order:
| Candidate | New Remainder |
|---|---|
| 3 | 3 |
DP confirms a valid completion exists, so choose 3.
State becomes:
| Mask | Remainder |
|---|---|
| 001 | 3 |
Next choices:
| Candidate | New Remainder |
|---|---|
| 12 | (3×100+12)%5=2 |
| 45 | (3×100+45)%5=0 |
The smaller candidate 12 works, so choose it.
State:
| Mask | Remainder |
|---|---|
| 011 | 2 |
Remaining number:
45
Final remainder:
(2×100+45)%5 = 0
Answer:
[3,12,45]
Example 2
nums = [10,5]
k = 10
Sorted order:
[5,10]
Start:
| Mask | Rem |
|---|---|
| 00 | 0 |
Choose 5:
rem = 5
Choose 10:
(5×100+10)%10 = 0
Answer:
[5,10]
Example 3
nums = [1,2,3]
k = 5
The DP explores every subset and remainder state.
No path reaches:
full_mask with remainder 0
Therefore:
dp(0,0) = false
and the answer is:
[]
return res
}
### Go-specific notes
The Go version replaces memoization via `lru_cache` with an explicit map keyed by `(mask, rem)`. Bit operations behave identically to Python, but integer division is explicit. Slices are used for dynamic arrays, and recursion depth is safe due to small state space.
## Worked Examples
### Example 1: nums = [3,12,45], k = 5
We compute:
- 3 → len=1, mod=3, pow10=10%5=0
- 12 → len=2, mod=2, pow10=100%5=0
- 45 → len=2, mod=0, pow10=0
From `(mask=000, rem=0)`:
We try `3`:
- rem = (0*0 + 3) % 5 = 3
From `(3, rem=3)` we continue similarly. DP confirms full completion possible.
Reconstruction tries smallest first:
1 → choose 3
2 → choose 12
3 → choose 45
Result `[3,12,45]`.
### Example 2: nums = [10,5], k = 10
Precompute:
- 10 → mod=0, len=2, pow10=100%10=0
- 5 → mod=5, len=1, pow10=10%10=0
From start:
Try 5 first:
- valid path exists → choose 5
Then 10.
Result `[5,10]`.
### Example 3: nums = [1,2,3], k = 5
DP explores all permutations but no path reaches final remainder 0.
Thus `can(0,0)` is false and we return `[]`.
## Complexity Analysis
| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(2^n · n · k) | Each state `(mask, rem)` is processed once |
| Space | O(2^n · k) | Memoization table stores all reachable states |
The DP state space contains at most:
2^n × k
states. For each state we may try up to `n` unused numbers. Since `n ≤ 13` and `k ≤ 100`, the solution comfortably fits within typical contest limits.
| Time | O(2^n · n · k) | Each state explores up to n transitions and has k possible remainders across mask space |
| Space | O(2^n · k) | Memoization table stores feasibility for each (mask, remainder) pair |
The exponential factor is unavoidable due to permutation structure, but bounded by `n ≤ 13`.
## Test Cases
sol = Solution()
assert sol.concatenatedDivisibility([3, 12, 45], 5) == [3, 12, 45] # example 1
assert sol.concatenatedDivisibility([10, 5], 10) == [5, 10] # example 2
assert sol.concatenatedDivisibility([1, 2, 3], 5) == [] # example 3
assert sol.concatenatedDivisibility([7], 7) == [7] # single valid element
assert sol.concatenatedDivisibility([7], 3) == [] # single invalid element
assert sol.concatenatedDivisibility([1, 10], 11) == [1, 10] # simple valid pair
assert sol.concatenatedDivisibility([10, 1], 11) == [1, 10] # lexicographically smallest
assert sol.concatenatedDivisibility([5, 5], 5) == [5, 5] # duplicates
assert sol.concatenatedDivisibility([100000, 99999], 1) == [99999, 100000] # k=1 always valid
assert sol.concatenatedDivisibility([9, 99, 999], 9) == [9, 99, 999] # many digit lengths
assert len(sol.concatenatedDivisibility(list(range(1, 14)), 1)) == 13 # maximum n
### Test Summary
| Test | Why |
| --- | --- |
| `[3,12,45], 5` | Official example |
| `[10,5], 10` | Official example with ordering change |
| `[1,2,3], 5` | No valid solution |
| `[7], 7` | Single-element valid case |
| `[7], 3` | Single-element invalid case |
| `[1,10], 11` | Small valid permutation |
| `[10,1], 11` | Lexicographic reconstruction |
| `[5,5], 5` | Duplicate values |
| `[100000,99999], 1` | Largest value sizes, always divisible |
| `[9,99,999], 9` | Multiple digit lengths |
| `range(1,14), 1` | Maximum allowed array size |
## Edge Cases
### No Valid Permutation Exists
Some inputs simply cannot produce a concatenation divisible by `k`. A common bug is reconstructing a path without first verifying that a valid solution exists. The implementation avoids this by checking `dp(0, 0)` before reconstruction. If that state is false, it immediately returns an empty list.
### Extremely Large Concatenated Numbers
The final concatenated value can contain dozens of digits, far exceeding standard integer limits. Constructing the full number repeatedly would be inefficient and potentially impossible. The solution stores only remainders modulo `k`, using the concatenation formula on remainders. This completely avoids large-number arithmetic.
### Multiple Valid Answers
There may be many valid permutations. Returning any valid permutation is not sufficient because the problem specifically requires the lexicographically smallest one. During reconstruction, candidates are tested in sorted order, and the first candidate that still permits a successful completion is selected. This guarantees lexicographic minimality.
### Duplicate Numbers
If duplicate values appear, multiple indices may contain the same number. The DP tracks used elements by index through the bitmask rather than by value. As a result, identical values are handled correctly and each occurrence is used exactly once.
### Maximum Constraint Size
With `n = 13`, brute-force permutation generation becomes impossible. The subset DP exploits the fact that `2^13 = 8192`, making a state space of approximately:
8192 × 100 = 819,200
which is manageable. This is precisely why the bitmask dynamic programming approach succeeds where brute force fails.
assert Solution().concatenatedDivisibility([3,12,45], 5) == [3,12,45] # basic example
assert Solution().concatenatedDivisibility([10,5], 10) == [5,10] # swap needed
assert Solution().concatenatedDivisibility([1,2,3], 5) == [] # no solution
assert Solution().concatenatedDivisibility([1], 1) == [1] # single element valid
assert Solution().concatenatedDivisibility([1], 2) == [] # single element invalid
assert Solution().concatenatedDivisibility([2,20,200], 2) != [] # multiple valid permutations exist
assert Solution().concatenatedDivisibility([9,91,910], 7) # structural stress case
| Test | Why |
|---|---|
| [3,12,45],5 | standard correctness |
| [10,5],10 | lexicographic swap constraint |
| [1,2,3],5 | infeasible case |
| [1],1 | minimal n |
| [1],2 | minimal n unsatisfiable |
| [2,20,200],2 | multiple valid paths |
| [9,91,910],7 | digit-length interaction stress |
Edge Cases
A single-element array is the simplest boundary condition. The DP must correctly treat the terminal condition where the mask already includes all elements and only accept it if the remainder is zero. Any incorrect handling of the base case leads to false positives.
Another important edge case is when multiple permutations are valid. In such cases, naive DFS may return the first found solution rather than the lexicographically smallest. The greedy reconstruction step is essential to enforce ordering.
Finally, cases with differing digit lengths, such as [1, 10, 100], can cause incorrect modulo transitions if powers of 10 are not precomputed correctly per element. Any mistake in computing 10^{len_i} mod k breaks the correctness of the state transition function.