Concatenated Divisibility

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.

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.