AntInLoop

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