Digit Dynamic Programming Code Implementations
Complete Digit Dynamic Programming code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Digit Dynamic Programming Guide · Launch Interactive Visualizer
C++ Implementation
// Digit DP Implementation in C++
#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
class DigitDP {
public:
// Count numbers with digit sum equal to target
static long long countNumbersWithDigitSum(long long n, int target) {
std::string numStr = std::to_string(n);
std::vector<int> digits;
for (char c : numStr) {
digits.push_back(c - '0');
}
std::unordered_map<std::string, long long> memo;
return dpDigitSum(digits, 0, true, 0, target, memo);
}
private:
static long long dpDigitSum(const std::vector<int>& digits, int pos, bool tight, int sum, int target,
std::unordered_map<std::string, long long>& memo) {
if (pos == digits.size()) {
return sum == target ? 1 : 0;
}
std::string key = std::to_string(pos) + "," + (tight ? "1" : "0") + "," + std::to_string(sum);
if (memo.find(key) != memo.end()) return memo[key];
long long result = 0;
int limit = tight ? digits[pos] : 9;
for (int d = 0; d <= limit; d++) {
bool newTight = tight && (d == digits[pos]);
int newSum = sum + d;
if (newSum <= target) {
result += dpDigitSum(digits, pos + 1, newTight, newSum, target, memo);
}
}
memo[key] = result;
return result;
}
public:
// Count numbers without consecutive 1s
static long long countNumbersWithoutConsecutiveOnes(long long n) {
std::string binaryStr;
while (n > 0) {
binaryStr = char('0' + (n % 2)) + binaryStr;
n /= 2;
}
std::vector<int> digits;
for (char c : binaryStr) {
digits.push_back(c - '0');
}
std::unordered_map<std::string, long long> memo;
return dpConsecutiveOnes(digits, 0, true, 0, memo);
}
private:
static long long dpConsecutiveOnes(const std::vector<int>& digits, int pos, bool tight, int prev,
std::unordered_map<std::string, long long>& memo) {
if (pos == digits.size()) return 1;
std::string key = std::to_string(pos) + "," + (tight ? "1" : "0") + "," + std::to_string(prev);
if (memo.find(key) != memo.end()) return memo[key];
long long result = 0;
int limit = tight ? digits[pos] : 1;
for (int d = 0; d <= limit; d++) {
if (prev == 1 && d == 1) continue;
bool newTight = tight && (d == digits[pos]);
result += dpConsecutiveOnes(digits, pos + 1, newTight, d, memo);
}
memo[key] = result;
return result;
}
public:
// Count numbers divisible by k
static long long countNumbersDivisibleByK(long long n, int k) {
std::string numStr = std::to_string(n);
std::vector<int> digits;
for (char c : numStr) {
digits.push_back(c - '0');
}
std::unordered_map<std::string, long long> memo;
return dpDivisibleByK(digits, 0, true, 0, k, memo);
}
private:
static long long dpDivisibleByK(const std::vector<int>& digits, int pos, bool tight, int rem, int k,
std::unordered_map<std::string, long long>& memo) {
if (pos == digits.size()) {
return rem == 0 ? 1 : 0;
}
std::string key = std::to_string(pos) + "," + (tight ? "1" : "0") + "," + std::to_string(rem);
if (memo.find(key) != memo.end()) return memo[key];
long long result = 0;
int limit = tight ? digits[pos] : 9;
for (int d = 0; d <= limit; d++) {
bool newTight = tight && (d == digits[pos]);
int newRem = (rem * 10 + d) % k;
result += dpDivisibleByK(digits, pos + 1, newTight, newRem, k, memo);
}
memo[key] = result;
return result;
}
public:
// Count numbers with exactly k distinct digits
static long long countNumbersWithKDistinctDigits(long long n, int k) {
std::string numStr = std::to_string(n);
std::vector<int> digits;
for (char c : numStr) {
digits.push_back(c - '0');
}
std::unordered_map<std::string, long long> memo;
return dpDistinctDigits(digits, 0, true, 0, 0, k, memo);
}
private:
static long long dpDistinctDigits(const std::vector<int>& digits, int pos, bool tight, int used, int count, int k,
std::unordered_map<std::string, long long>& memo) {
if (pos == digits.size()) {
return count == k ? 1 : 0;
}
std::string key = std::to_string(pos) + "," + (tight ? "1" : "0") + "," + std::to_string(used) + "," + std::to_string(count);
if (memo.find(key) != memo.end()) return memo[key];
long long result = 0;
int limit = tight ? digits[pos] : 9;
for (int d = 0; d <= limit; d++) {
bool newTight = tight && (d == digits[pos]);
int newUsed = used | (1 << d);
int newCount = (used & (1 << d)) ? count : count + 1;
if (newCount <= k) {
result += dpDistinctDigits(digits, pos + 1, newTight, newUsed, newCount, k, memo);
}
}
memo[key] = result;
return result;
}
public:
// Count numbers with digit product equal to target
static long long countNumbersWithDigitProduct(long long n, long long target) {
std::string numStr = std::to_string(n);
std::vector<int> digits;
for (char c : numStr) {
digits.push_back(c - '0');
}
std::unordered_map<std::string, long long> memo;
return dpDigitProduct(digits, 0, true, 1, target, memo);
}
private:
static long long dpDigitProduct(const std::vector<int>& digits, int pos, bool tight, long long product, long long target,
std::unordered_map<std::string, long long>& memo) {
if (pos == digits.size()) {
return product == target ? 1 : 0;
}
std::string key = std::to_string(pos) + "," + (tight ? "1" : "0") + "," + std::to_string(product);
if (memo.find(key) != memo.end()) return memo[key];
long long result = 0;
int limit = tight ? digits[pos] : 9;
for (int d = 0; d <= limit; d++) {
bool newTight = tight && (d == digits[pos]);
long long newProduct = product * d;
if (newProduct <= target) {
result += dpDigitProduct(digits, pos + 1, newTight, newProduct, target, memo);
}
}
memo[key] = result;
return result;
}
public:
// Performance comparison
static void comparePerformance(long long n, int target) {
auto start = std::chrono::high_resolution_clock::now();
long long result1 = countNumbersWithDigitSum(n, target);
auto end = std::chrono::high_resolution_clock::now();
auto duration1 = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
start = std::chrono::high_resolution_clock::now();
long long result2 = countNumbersDivisibleByK(n, target);
end = std::chrono::high_resolution_clock::now();
auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
std::cout << "Digit Sum: " << result1 << " (" << duration1.count() << " μs)" << std::endl;
std::cout << "Divisible by K: " << result2 << " (" << duration2.count() << " μs)" << std::endl;
}
};JAVA Implementation
// Digit DP Implementation in Java
import java.util.*;
public class DigitDP {
// Count numbers with digit sum equal to target
public static long countNumbersWithDigitSum(long n, int target) {
String numStr = String.valueOf(n);
int[] digits = new int[numStr.length()];
for (int i = 0; i < numStr.length(); i++) {
digits[i] = numStr.charAt(i) - '0';
}
Map<String, Long> memo = new HashMap<>();
return dpDigitSum(digits, 0, true, 0, target, memo);
}
private static long dpDigitSum(int[] digits, int pos, boolean tight, int sum, int target, Map<String, Long> memo) {
if (pos == digits.length) {
return sum == target ? 1 : 0;
}
String key = pos + "," + tight + "," + sum;
if (memo.containsKey(key)) return memo.get(key);
long result = 0;
int limit = tight ? digits[pos] : 9;
for (int d = 0; d <= limit; d++) {
boolean newTight = tight && (d == digits[pos]);
int newSum = sum + d;
if (newSum <= target) {
result += dpDigitSum(digits, pos + 1, newTight, newSum, target, memo);
}
}
memo.put(key, result);
return result;
}
// Count numbers without consecutive 1s
public static long countNumbersWithoutConsecutiveOnes(long n) {
String binaryStr = Long.toBinaryString(n);
int[] digits = new int[binaryStr.length()];
for (int i = 0; i < binaryStr.length(); i++) {
digits[i] = binaryStr.charAt(i) - '0';
}
Map<String, Long> memo = new HashMap<>();
return dpConsecutiveOnes(digits, 0, true, 0, memo);
}
private static long dpConsecutiveOnes(int[] digits, int pos, boolean tight, int prev, Map<String, Long> memo) {
if (pos == digits.length) return 1;
String key = pos + "," + tight + "," + prev;
if (memo.containsKey(key)) return memo.get(key);
long result = 0;
int limit = tight ? digits[pos] : 1;
for (int d = 0; d <= limit; d++) {
if (prev == 1 && d == 1) continue;
boolean newTight = tight && (d == digits[pos]);
result += dpConsecutiveOnes(digits, pos + 1, newTight, d, memo);
}
memo.put(key, result);
return result;
}
// Count numbers divisible by k
public static long countNumbersDivisibleByK(long n, int k) {
String numStr = String.valueOf(n);
int[] digits = new int[numStr.length()];
for (int i = 0; i < numStr.length(); i++) {
digits[i] = numStr.charAt(i) - '0';
}
Map<String, Long> memo = new HashMap<>();
return dpDivisibleByK(digits, 0, true, 0, k, memo);
}
private static long dpDivisibleByK(int[] digits, int pos, boolean tight, int rem, int k, Map<String, Long> memo) {
if (pos == digits.length) {
return rem == 0 ? 1 : 0;
}
String key = pos + "," + tight + "," + rem;
if (memo.containsKey(key)) return memo.get(key);
long result = 0;
int limit = tight ? digits[pos] : 9;
for (int d = 0; d <= limit; d++) {
boolean newTight = tight && (d == digits[pos]);
int newRem = (rem * 10 + d) % k;
result += dpDivisibleByK(digits, pos + 1, newTight, newRem, k, memo);
}
memo.put(key, result);
return result;
}
// Count numbers with exactly k distinct digits
public static long countNumbersWithKDistinctDigits(long n, int k) {
String numStr = String.valueOf(n);
int[] digits = new int[numStr.length()];
for (int i = 0; i < numStr.length(); i++) {
digits[i] = numStr.charAt(i) - '0';
}
Map<String, Long> memo = new HashMap<>();
return dpDistinctDigits(digits, 0, true, 0, 0, k, memo);
}
private static long dpDistinctDigits(int[] digits, int pos, boolean tight, int used, int count, int k, Map<String, Long> memo) {
if (pos == digits.length) {
return count == k ? 1 : 0;
}
String key = pos + "," + tight + "," + used + "," + count;
if (memo.containsKey(key)) return memo.get(key);
long result = 0;
int limit = tight ? digits[pos] : 9;
for (int d = 0; d <= limit; d++) {
boolean newTight = tight && (d == digits[pos]);
int newUsed = used | (1 << d);
int newCount = (used & (1 << d)) != 0 ? count : count + 1;
if (newCount <= k) {
result += dpDistinctDigits(digits, pos + 1, newTight, newUsed, newCount, k, memo);
}
}
memo.put(key, result);
return result;
}
// Count numbers with digit product equal to target
public static long countNumbersWithDigitProduct(long n, long target) {
String numStr = String.valueOf(n);
int[] digits = new int[numStr.length()];
for (int i = 0; i < numStr.length(); i++) {
digits[i] = numStr.charAt(i) - '0';
}
Map<String, Long> memo = new HashMap<>();
return dpDigitProduct(digits, 0, true, 1, target, memo);
}
private static long dpDigitProduct(int[] digits, int pos, boolean tight, long product, long target, Map<String, Long> memo) {
if (pos == digits.length) {
return product == target ? 1 : 0;
}
String key = pos + "," + tight + "," + product;
if (memo.containsKey(key)) return memo.get(key);
long result = 0;
int limit = tight ? digits[pos] : 9;
for (int d = 0; d <= limit; d++) {
boolean newTight = tight && (d == digits[pos]);
long newProduct = product * d;
if (newProduct <= target) {
result += dpDigitProduct(digits, pos + 1, newTight, newProduct, target, memo);
}
}
memo.put(key, result);
return result;
}
}JAVASCRIPT Implementation
// Digit DP Implementation in JavaScript
// Count numbers with digit sum equal to target
function countNumbersWithDigitSum(n, target) {
const digits = n.toString().split('').map(Number);
const memo = new Map();
function dp(pos, tight, sum) {
if (pos === digits.length) {
return sum === target ? 1 : 0;
}
const key = pos + ',' + tight + ',' + sum;
if (memo.has(key)) return memo.get(key);
let result = 0;
const limit = tight ? digits[pos] : 9;
for (let d = 0; d <= limit; d++) {
const newTight = tight && (d === digits[pos]);
const newSum = sum + d;
if (newSum <= target) {
result += dp(pos + 1, newTight, newSum);
}
}
memo.set(key, result);
return result;
}
return dp(0, true, 0);
}
// Count numbers without consecutive 1s
function countNumbersWithoutConsecutiveOnes(n) {
const digits = n.toString(2).split('').map(Number);
const memo = new Map();
function dp(pos, tight, prev) {
if (pos === digits.length) return 1;
const key = pos + ',' + tight + ',' + prev;
if (memo.has(key)) return memo.get(key);
let result = 0;
const limit = tight ? digits[pos] : 1;
for (let d = 0; d <= limit; d++) {
if (prev === 1 && d === 1) continue;
const newTight = tight && (d === digits[pos]);
result += dp(pos + 1, newTight, d);
}
memo.set(key, result);
return result;
}
return dp(0, true, 0);
}
// Count numbers divisible by k
function countNumbersDivisibleByK(n, k) {
const digits = n.toString().split('').map(Number);
const memo = new Map();
function dp(pos, tight, rem) {
if (pos === digits.length) {
return rem === 0 ? 1 : 0;
}
const key = pos + ',' + tight + ',' + rem;
if (memo.has(key)) return memo.get(key);
let result = 0;
const limit = tight ? digits[pos] : 9;
for (let d = 0; d <= limit; d++) {
const newTight = tight && (d === digits[pos]);
const newRem = (rem * 10 + d) % k;
result += dp(pos + 1, newTight, newRem);
}
memo.set(key, result);
return result;
}
return dp(0, true, 0);
}
// Count numbers with exactly k distinct digits
function countNumbersWithKDistinctDigits(n, k) {
const digits = n.toString().split('').map(Number);
const memo = new Map();
function dp(pos, tight, used, count) {
if (pos === digits.length) {
return count === k ? 1 : 0;
}
const key = pos + ',' + tight + ',' + used + ',' + count;
if (memo.has(key)) return memo.get(key);
let result = 0;
const limit = tight ? digits[pos] : 9;
for (let d = 0; d <= limit; d++) {
const newTight = tight && (d === digits[pos]);
const newUsed = used | (1 << d);
const newCount = used & (1 << d) ? count : count + 1;
if (newCount <= k) {
result += dp(pos + 1, newTight, newUsed, newCount);
}
}
memo.set(key, result);
return result;
}
return dp(0, true, 0, 0);
}
// Count numbers with digit product equal to target
function countNumbersWithDigitProduct(n, target) {
const digits = n.toString().split('').map(Number);
const memo = new Map();
function dp(pos, tight, product) {
if (pos === digits.length) {
return product === target ? 1 : 0;
}
const key = pos + ',' + tight + ',' + product;
if (memo.has(key)) return memo.get(key);
let result = 0;
const limit = tight ? digits[pos] : 9;
for (let d = 0; d <= limit; d++) {
const newTight = tight && (d === digits[pos]);
const newProduct = product * d;
if (newProduct <= target) {
result += dp(pos + 1, newTight, newProduct);
}
}
memo.set(key, result);
return result;
}
return dp(0, true, 1);
}PYTHON Implementation
# Digit DP Implementation in Python
from functools import lru_cache
def count_numbers_with_digit_sum(n, target):
digits = list(map(int, str(n)))
@lru_cache(maxsize=None)
def dp(pos, tight, sum_val):
if pos == len(digits):
return 1 if sum_val == target else 0
result = 0
limit = digits[pos] if tight else 9
for d in range(limit + 1):
new_tight = tight and (d == digits[pos])
new_sum = sum_val + d
if new_sum <= target:
result += dp(pos + 1, new_tight, new_sum)
return result
return dp(0, True, 0)
def count_numbers_without_consecutive_ones(n):
digits = list(map(int, bin(n)[2:]))
@lru_cache(maxsize=None)
def dp(pos, tight, prev):
if pos == len(digits):
return 1
result = 0
limit = digits[pos] if tight else 1
for d in range(limit + 1):
if prev == 1 and d == 1:
continue
new_tight = tight and (d == digits[pos])
result += dp(pos + 1, new_tight, d)
return result
return dp(0, True, 0)
def count_numbers_divisible_by_k(n, k):
digits = list(map(int, str(n)))
@lru_cache(maxsize=None)
def dp(pos, tight, rem):
if pos == len(digits):
return 1 if rem == 0 else 0
result = 0
limit = digits[pos] if tight else 9
for d in range(limit + 1):
new_tight = tight and (d == digits[pos])
new_rem = (rem * 10 + d) % k
result += dp(pos + 1, new_tight, new_rem)
return result
return dp(0, True, 0)
def count_numbers_with_k_distinct_digits(n, k):
digits = list(map(int, str(n)))
@lru_cache(maxsize=None)
def dp(pos, tight, used, count):
if pos == len(digits):
return 1 if count == k else 0
result = 0
limit = digits[pos] if tight else 9
for d in range(limit + 1):
new_tight = tight and (d == digits[pos])
new_used = used | (1 << d)
new_count = count if used & (1 << d) else count + 1
if new_count <= k:
result += dp(pos + 1, new_tight, new_used, new_count)
return result
return dp(0, True, 0, 0)
def count_numbers_with_digit_product(n, target):
digits = list(map(int, str(n)))
@lru_cache(maxsize=None)
def dp(pos, tight, product):
if pos == len(digits):
return 1 if product == target else 0
result = 0
limit = digits[pos] if tight else 9
for d in range(limit + 1):
new_tight = tight and (d == digits[pos])
new_product = product * d
if new_product <= target:
result += dp(pos + 1, new_tight, new_product)
return result
return dp(0, True, 1)
# Additional digit DP utilities
def get_digits(n):
return list(map(int, str(n)))
def get_binary_digits(n):
return list(map(int, bin(n)[2:]))
def count_digits_with_condition(n, condition_func):
digits = get_digits(n)
@lru_cache(maxsize=None)
def dp(pos, tight, state):
if pos == len(digits):
return 1 if condition_func(state) else 0
result = 0
limit = digits[pos] if tight else 9
for d in range(limit + 1):
new_tight = tight and (d == digits[pos])
new_state = update_state(state, d)
result += dp(pos + 1, new_tight, new_state)
return result
return dp(0, True, initial_state())
def update_state(state, digit):
# Customize based on problem
return state + digit
def initial_state():
# Customize based on problem
return 0