Pattern Guide
Carry & Digit Manipulation DP
"DP tracking carries in arithmetic operations. Count valid assignments with constraints."
Carry DP handles problems involving arithmetic column-by-column with carry state: count valid digit assignments where columns satisfy constraints, verify if a sum is achievable, or minimize operations involving carries. Also covers digit sum tricks, parity tracking, and number construction problems where you process digits from least significant to most significant.
Problems you can solve with this pattern
3 problems · click any to start solving
// Count ways to assign k-digit values to n variables so their sum = target
// Each variable's digit can be 0-9 in each position
// Process position by position (from LSB), tracking carry
function countValidAssignments(n, target, numDigits) {
// dp[carry] = number of ways to achieve this carry after processing current digit position
let dp = new Map([[0, 1]]); // initial state: carry = 0
// Process each digit position
for (let pos = 0; pos < numDigits; pos++) {
const targetDigit = Math.floor(target / Math.pow(10, pos)) % 10;
const newDp = new Map();
for (const [carry, ways] of dp) {
// Try all possible sums for this column (0 to 9*n)
// The n variables each contribute one digit
for (let colSum = 0; colSum <= 9 * n; colSum++) {
const total = colSum + carry;
const outDigit = total % 10;
const newCarry = Math.floor(total / 10);
if (outDigit === targetDigit) {
// Count assignments giving colSum in n variables
const assignments = countDigitCombinations(n, colSum, 0, 9);
newDp.set(newCarry, (newDp.get(newCarry) || 0) + ways * assignments);
}
}
}
dp = newDp;
}
return dp.get(0) || 0; // must finish with carry = 0
}Carry DP processes arithmetic column by column. State: carry value (typically 0 or 1 for binary, 0..9 for decimal). Transition: for each column, sum of column digits + incoming carry = column result + 10 × outgoing carry. Count valid digit assignments or verify feasibility. Digit sum DP is a special case: digits must satisfy a target sum, optionally with the tight constraint from digit DP.
// Count ways to assign k-digit values to n variables so their sum = target
// Each variable's digit can be 0-9 in each position
// Process position by position (from LSB), tracking carry
function countValidAssignments(n, target, numDigits) {
// dp[carry] = number of ways to achieve this carry after processing current digit position
let dp = new Map([[0, 1]]); // initial state: carry = 0
// Process each digit position
for (let pos = 0; pos < numDigits; pos++) {
const targetDigit = Math.floor(target / Math.pow(10, pos)) % 10;
const newDp = new Map();
for (const [carry, ways] of dp) {
// Try all possible sums for this column (0 to 9*n)
// The n variables each contribute one digit
for (let colSum = 0; colSum <= 9 * n; colSum++) {
const total = colSum + carry;
const outDigit = total % 10;
const newCarry = Math.floor(total / 10);
if (outDigit === targetDigit) {
// Count assignments giving colSum in n variables
const assignments = countDigitCombinations(n, colSum, 0, 9);
newDp.set(newCarry, (newDp.get(newCarry) || 0) + ways * assignments);
}
}
}
dp = newDp;
}
return dp.get(0) || 0; // must finish with carry = 0
}Digit sum DP: More general — count numbers with specific digit sum, sum within range, etc. State = (position, current_sum, tight_bound, leading_zero).
Common patterns:
- Column verification: does a digit assignment satisfy arithmetic constraint?
- Count valid n-tuples: n variables summing to target in each column
- Number reconstruction: build number digit by digit satisfying constraints