Find the Largest Palindrome Divisible by K

Treat a length-n palindrome as choices for its first ceiling(n/2) digits, with each choice contributing to two mirrored decimal positions except the center. Precompute each position's coefficient modulo k using powers of ten, then use a suffix feasibility DP: reachable[pos][remainder] says whether choices from pos onward can add a residue that completes divisibility. Construct greedily from the most significant position, trying digits from nine down to zero, rejecting leading zero and retaining the first digit whose contribution leaves a reachable suffix residue. This greedy choice is safe because all later digits are less significant and the DP proves feasibility. The exact constraints matter: if n is huge and k is small, residues make the state manageable; if k is large, a different formulation may be needed. Test n one, even and odd lengths, k one, and cases with no valid leading digit. With h=ceil(n/2), the DP is O(hk10) time and O(h*k) space.