This problem requires constructing the lexicographically smallest sequence of numbers whose concatenated value is divisible by k. Using state transition dynamic programming combined with bitmasking, we track which numbers are used and the current remainder modulo k. Recursive exploration with memoization ensures all valid permutations are considered efficiently while pruning invalid paths early.
Problem Statement
Given an array of positive integers nums and a positive integer k, find a permutation of nums such that concatenating the numbers in order results in a number divisible by k. The goal is to return the lexicographically smallest valid permutation. If no permutation exists, return an empty list.
For example, nums = [3,12,45] and k = 5 yields [3,12,45] because concatenating them produces a number divisible by 5. Constraints are 1 <= nums.length <= 13, 1 <= nums[i] <= 105, and 1 <= k <= 100.
Examples
Example 1
Input: nums = [3,12,45], k = 5
Output: [3,12,45]
The lexicographically smallest permutation that forms a divisible concatenation is [3,12,45] .
Example 2
Input: nums = [10,5], k = 10
Output: [5,10]
The lexicographically smallest permutation that forms a divisible concatenation is [5,10] .
Example 3
Input: nums = [1,2,3], k = 5
Output: []
Since no permutation of nums forms a valid divisible concatenation, return an empty list.
Constraints
- 1 <= nums.length <= 13
- 1 <= nums[i] <= 105
- 1 <= k <= 100
Solution Approach
Precompute Modular Powers
Calculate the length of each number and precompute 10^len mod k for each to quickly evaluate new remainders when concatenating numbers in different orders.
Recursive State Transition DP
Use a DP function dp(mask, remainder) where mask tracks used numbers and remainder is current modulo k. Try all unused numbers, updating remainder, and recurse to find valid permutations.
Memoization and Lexicographical Ordering
Memoize states to avoid recomputation and always explore numbers in ascending order to ensure the final sequence is lexicographically smallest. Return the constructed permutation when remainder is zero and all numbers are used.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n * 2^n * k) due to iterating over all subsets of numbers with DP and computing remainders. Space complexity is O(2^n * k) for memoization of all state transitions.
What Interviewers Usually Probe
- Asks if recursive DP with bitmasking can cover all permutations efficiently.
- Questions how remainder modulo k is updated when concatenating numbers.
- Checks if lexicographical order is preserved during state transitions.
Common Pitfalls or Variants
Common pitfalls
- Failing to precompute modular powers, causing slow remainder calculations.
- Not memoizing DP states, leading to exponential runtime.
- Ignoring lexicographical order and returning a valid but non-minimal permutation.
Follow-up variants
- Return the count of all valid permutations forming divisible concatenations instead of one sequence.
- Allow repeated numbers in nums and find the smallest concatenation divisible by k.
- Change k to a large prime and analyze how bitmask DP scales with modulo operations.
How GhostInterview Helps
- Identifies the correct DP state representation and mask encoding for tracking used numbers.
- Guides through remainder calculation with modular arithmetic to avoid large number issues.
- Ensures exploration order produces the lexicographically smallest valid permutation efficiently.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What pattern does Concatenated Divisibility follow?
It follows state transition dynamic programming with bitmasking to track used elements and current modulo k.
Can nums contain zeros or large numbers?
Yes, nums can include numbers up to 105, but all are positive integers; zeros do not appear alone.
Why is memoization necessary in this DP solution?
Without memoization, recursive exploration of all 2^n subsets would be too slow for n up to 13.
How is lexicographical order maintained?
Always iterate numbers in ascending order when choosing the next element in the DP recursion.
What if no permutation forms a divisible concatenation?
Return an empty list as specified in the problem statement.
Need direct help with Concatenated Divisibility instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Concatenated Divisibility from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Solve the Maximum Profit from Valid Topological Order in DAG problem using graph indegree and topological sorting with dynamic programming.
Open problem page#3539 Find Sum of Array Product of Magical SequencesUse state transition dynamic programming to count magical index sequences and accumulate weighted products without enumerating exponential orderings.
Open problem page#3575 Maximum Good Subtree ScoreFind the maximum sum of values in a tree subtree without repeating any digit across selected nodes using DFS and bitmasking.
Open problem page