Concatenated Divisibility - Video Solutions
Concatenated Divisibility | Leetcode Weekly Contest 447 | Problem C | DP Bitmasking | Leetcode 3533
Concatenated Divisibility - Video Solution
Watch 4 video solutions for Concatenated Divisibility, a hard level problem involving Array, Dynamic Programming, Bit Manipulation. This walkthrough by Lazy Coders has 271 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
Complexity 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 |