- Define precisely what one DP state represents.
- Establish the base cases before transitions are evaluated.
- Process states in dependency order and combine only already-known values.
Code notes
- 36 lines of Python from the credited upstream file 3533.py.
- The implementation visibly relies on sequence storage, cached states.
- No explicit loop blocks detected.
Complexity
Multiply the number of reachable states by the work performed for each transition, then include the stored state table in memory usage.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1class Solution:2 def concatenatedDivisibility(self, nums: list[int], k: int) -> list[int]:3 n = len(nums)4 nums.sort()5 lengths = [len(str(num)) for num in nums]6 pows = [pow(10, length, k) for length in lengths]7 8 @functools.lru_cache(None)9 def dp(mask: int, mod: int) -> bool:10 """11 Returns True if there is a way to form a number divisible by `k` using the12 numbers in `nums`, where nums[i] is used iff `mask & (1 << i)`.13 """14 if mask == (1 << n) - 1:15 return mod == 016 for i in range(n):17 if (mask >> i & 1) == 0:18 newMod = (mod * pows[i] + nums[i]) % k19 if dp(mask | 1 << i, newMod):20 return True21 return False22 23 def reconstruct(mask: int, mod: int) -> list[int]:24 """25 Reconstructs the numbers that form a number divisible by `k` using the26 numbers in `nums`, where nums[i] is used iff `mask & (1 << i)`.27 """28 for i in range(n):29 if (mask >> i & 1) == 0:30 newMod = (mod * pows[i] + nums[i]) % k31 if dp(mask | 1 << i, newMod):32 return [nums[i]] + reconstruct(mask | 1 << i, newMod)33 return []34 35 return reconstruct(0, 0) if dp(0, 0) else []36