Concatenated Divisibility - Solution & Explanation

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.