Concatenated Divisibility solution and explanation
3 more videos on this problem
Concatenated Divisibility | Leetcode Weekly Contest 447 | Problem C | DP Bitmasking | Leetcode 3533Lazy Coders · 1:29:56 · 271 views
3533. Concatenated Divisibility (Leetcode Hard)Programming Live with Larry · 19:42 · 253 views
leetcode 3533 Concatenated Divisibility | recursive backtracking with bitmaskCode-Yao · 14:39 · 115 views
Q3 ✅ Concatenated Divisibility ✅ |LeetCode Weekly Contest 447 | All Solutions ✅Learning Unique · 0:24 · 103 views
The 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.
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] <= 1051 <= k <= 100
Approach overview
Problem Overview: You are given an array of numbers and need to determine whether some ordering of them forms a concatenated integer divisible by k. The challenge is that concatenation changes magnitude, so every permutation creates a different value. A brute force permutation check quickly becomes infeasible.
Approach 1: Brute Force Permutations (O(n! * L), Space O(n))
Generate every permutation of the array and build the concatenated number for each ordering. After forming the number, compute its remainder modulo k. If any permutation produces remainder 0, the condition is satisfied. This approach directly simulates the problem but scales poorly because the number of permutations grows factorially. Even with small arrays (n ≈ 10), the runtime becomes impractical.
Approach 2: Bitmask Dynamic Programming with Remainders (O(n * 2^n * k), Space O(2^n * k))
The optimal strategy avoids recomputing concatenations by tracking remainders. Use a DP state dp[mask][rem] where mask represents which elements are already used and rem is the current remainder modulo k after concatenating them. When adding a new number nums[i], compute the new remainder using modular arithmetic: multiply the current remainder by 10^len(nums[i]), add the value, then take modulo k. Precompute powers of 10 modulo k to make this constant time. Iterate through all masks and try appending each unused element. This reduces the exponential permutation space to 2^n states.
This solution relies heavily on bitmask representation to encode subsets and dynamic programming to reuse partial results. Modular arithmetic ensures that the algorithm never constructs the full concatenated integer, avoiding overflow.
Approach 3: Bitmask DP with Precomputed Transition Remainders (O(n * 2^n), Space O(2^n * n))
A further optimization precomputes how each number affects every possible remainder. For each element i and remainder r, compute the resulting remainder after concatenation. During DP transitions you only perform a table lookup instead of modular arithmetic. This reduces constant factors and is useful when k is large or the concatenated numbers contain many digits.
Recommended for interviews: The bitmask DP with remainder tracking is the expected solution. Brute force permutations demonstrate understanding of the problem but fail scalability tests. The DP formulation shows mastery of subset states, modular arithmetic, and optimization techniques common in bit manipulation problems.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Permutations | O(n! * L) | O(n) | Small arrays where n ≤ 8 and simplicity matters |
| Bitmask DP with Remainder Tracking | O(n * 2^n * k) | O(2^n * k) | General optimal solution for permutations with divisibility constraints |
| Bitmask DP with Precomputed Transitions | O(n * 2^n) | O(2^n * n) | Large k or frequent remainder transitions where constant-factor optimization helps |
Frequently asked questions
Is Concatenated Divisibility easy or hard?
Concatenated Divisibility is considered a hard problem because it combines permutations, modular arithmetic, and bitmask dynamic programming. The key difficulty is recognizing that concatenation effects can be tracked using remainders rather than constructing the full number.
Concatenated Divisibility Python/Java solution
Python, Java, C++, and Go implementations typically follow the same pattern: precompute digit lengths and powers of 10 modulo k, initialize a DP table for mask and remainder states, and iterate through subsets while updating remainders when appending numbers.
How to solve Concatenated Divisibility in O(n * 2^n)?
Use bitmask DP and precompute how each number affects every possible remainder modulo k. Instead of recomputing modular concatenation each time, store transition results in a lookup table. DP transitions then become constant-time operations, reducing the complexity to roughly O(n * 2^n) with preprocessing.
What is the best approach for Concatenated Divisibility?
The best approach uses bitmask dynamic programming with remainder tracking. Each DP state represents a subset of used numbers and the current remainder modulo k after concatenation. Transitions append unused numbers and update the remainder using modular arithmetic. This reduces factorial permutations to about O(n * 2^n * k) states.
Is Concatenated Divisibility asked at Google/Amazon/Meta?
Permutation problems combined with bitmask dynamic programming frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving divisibility, subset states, or remainder tracking are common in senior-level algorithm rounds.
What data structure is used in Concatenated Divisibility?
The main data structure is a dynamic programming table indexed by bitmask and remainder. Bitmasks represent which array elements are already used, while the remainder dimension tracks the current value modulo k. Precomputed arrays for powers of 10 modulo k are also typically used.
What is the time complexity of Concatenated Divisibility?
The optimal solution runs in O(n * 2^n * k) time with O(2^n * k) space. The algorithm iterates through every subset of elements (2^n states) and attempts to append each unused number while updating the remainder modulo k.