Digit Sum

Problem Overview

Learning Goals

After solving this problem, you will be able to:

• Understand the digit DP framework and when to apply it
• Handle “tight” constraints when building numbers digit by digit
• Track modular remainders efficiently as DP states
• Count numbers in a range satisfying digit-based conditions

Problem Statement

Problem: Given a string K representing a positive integer and an integer D, count how many positive integers less than or equal to K have a digit sum divisible by D. Return the count modulo 10^9 + 7.

Input:

• Line 1: K (a string representing a positive integer)
• Line 2: D (the divisor)

Output:

• A single integer: the count modulo 10^9 + 7

Constraints:

• 1 <=

  K

  <= 10^4 (K can have up to 10,000 digits)

• 1 <= D <= 100

Example

Input:
30
4

Output:
6

Explanation: The numbers from 1 to 30 with digit sum divisible by 4 are: 4, 8, 13, 17, 22, 26. Their digit sums are 4, 8, 4, 8, 4, 8 respectively, all divisible by 4.

Intuition: How to Think About This Problem

Pattern Recognition

Key Question: How do we count numbers up to K with a specific digit property when K is too large to iterate?

This is a classic digit DP problem. We cannot iterate through all numbers from 1 to K since K can have up to 10,000 digits. Instead, we build numbers digit by digit and use DP to count valid configurations.

Breaking Down the Problem

1. What are we looking for? Count of numbers in [1, K] where digit_sum % D == 0
2. What information do we have? The upper bound K and divisor D
3. What’s the relationship? We need to track partial digit sums modulo D as we construct numbers

The Digit DP Framework

Think of building a number digit by digit from left to right. At each position, we need to know:

1. Position: Which digit are we filling?
2. Tight constraint: Can we still pick any digit, or are we bounded by K?
3. Current state: What is our digit sum so far (modulo D)?

Solution: Digit DP

Key Insight

The Trick: Build numbers digit by digit, tracking (position, is_tight, sum_mod_D) to count valid numbers without enumeration.

DP State Definition

• pos: Current digit position (0 to n-1)
• tight: Whether we’re still bounded by K (1) or free to choose any digit (0)
• sum_mod: Current digit sum modulo D

In plain English: How many ways can we fill the remaining digits such that the final digit sum is divisible by D?

State Transition

For each digit d in [0, limit]:
    new_tight = tight AND (d == K[pos])
    new_sum = (sum_mod + d) % D
    dp[pos][tight][sum_mod] += dp[pos+1][new_tight][new_sum]

Why? When tight=1, we can only choose digits up to K[pos]. Once we choose a smaller digit, we become “free” (tight=0) and can use digits 0-9 for remaining positions.

Base Cases

Algorithm

1. Convert K to array of digits
2. Use memoization/tabulation for states (pos, tight, sum_mod)
3. For each state, try all valid digits and recurse
4. Subtract 1 from result (to exclude 0) and return

Dry Run Example

Let’s trace through with K = "30", D = 4:

K = "30", digits = [3, 0], D = 4, n = 2

Call dp(pos=0, tight=1, sum_mod=0):
  limit = 3 (tight, so bounded by K[0])

  d=0: dp(1, 0, 0)  -> sum_mod=0
  d=1: dp(1, 0, 1)  -> sum_mod=1
  d=2: dp(1, 0, 2)  -> sum_mod=2
  d=3: dp(1, 1, 3)  -> sum_mod=3, still tight

For dp(1, 0, 0) [not tight, sum=0]:
  limit = 9 (free to choose any digit)
  d=0: sum=0, divisible by 4? YES -> count 1 (number "00")
  d=4: sum=4, divisible by 4? YES -> count 1 (number "04")
  d=8: sum=8, divisible by 4? YES -> count 1 (number "08")
  ... = 3 valid numbers

For dp(1, 0, 1) [not tight, sum=1]:
  d=3: sum=4, YES -> count 1 (number "13")
  d=7: sum=8, YES -> count 1 (number "17")
  ... = 2 valid numbers

For dp(1, 0, 2) [not tight, sum=2]:
  d=2: sum=4, YES -> count 1 (number "22")
  d=6: sum=8, YES -> count 1 (number "26")
  ... = 2 valid numbers

For dp(1, 1, 3) [tight, sum=3]:
  limit = 0 (bounded by K[1]=0)
  d=0: sum=3, NOT divisible by 4 -> 0

Total from dp(0,1,0) = 3+2+2+0 = 7
Subtract 1 for "00" (we want 1 to K, not 0 to K)
Final answer: 7 - 1 = 6

Visual Diagram

Building numbers <= 30 digit by digit:

Position:    0       1
K digits:   [3]     [0]
             |       |
             v       v
        +---+---+   +-----------+
tight=1 |0|1|2|3|   | 0 only    | (when first digit is 3)
        +-+-+-+-+   +-----------+
          | | |
          v v v
tight=0   +-------+
          |0-9    | (when first digit < 3)
          +-------+

Track: sum_mod_D at each step
Goal: sum_mod == 0 at the end

Code (Python)

def solve():
  """
  Digit DP solution for counting numbers with digit sum divisible by D.

  Time: O(n * 2 * D * 10) = O(n * D)
  Space: O(n * D) for memoization
  """
  MOD = 10**9 + 7

  K = input().strip()
  D = int(input().strip())

  n = len(K)
  digits = [int(c) for c in K]

  # Memoization: (pos, tight, sum_mod) -> count
  memo = {}

  def dp(pos, tight, sum_mod):
    # Base case: all digits processed
    if pos == n:
      return 1 if sum_mod == 0 else 0

    state = (pos, tight, sum_mod)
    if state in memo:
      return memo[state]

    # Determine digit range
    limit = digits[pos] if tight else 9

    result = 0
    for d in range(limit + 1):
      new_tight = tight and (d == limit)
      new_sum = (sum_mod + d) % D
      result = (result + dp(pos + 1, new_tight, new_sum)) % MOD

    memo[state] = result
    return result

  # dp(0, True, 0) counts numbers from 0 to K
  # Subtract 1 to exclude 0 (we want 1 to K)
  ans = (dp(0, True, 0) - 1 + MOD) % MOD
  print(ans)

if __name__ == "__main__":
  solve()

Complexity

Common Mistakes

Mistake 1: Forgetting to Exclude Zero

# WRONG
ans = dp(0, True, 0)  # Includes 0 in the count

# CORRECT
ans = (dp(0, True, 0) - 1 + MOD) % MOD  # Exclude 0

Problem: The digit DP counts from 0 to K, but we want 1 to K. Fix: Subtract 1 from the result (with proper modulo handling).

Mistake 2: Incorrect Tight Transition

# WRONG
new_tight = (d == limit)  # Forgets to check if already tight

# CORRECT
new_tight = tight and (d == limit)

Problem: Once we’re not tight, we stay not tight. Fix: Only remain tight if we were tight AND chose the max digit.

Mistake 3: Negative Modulo

# WRONG
ans = (dp(0, True, 0) - 1) % MOD  # Can be negative!

# CORRECT
ans = (dp(0, True, 0) - 1 + MOD) % MOD  # Always positive

Problem: In some languages, (-1) % MOD can be negative. Fix: Add MOD before taking modulo.

Edge Cases

When to Use This Pattern

Use Digit DP When:

• Counting numbers in range [0, K] with digit-based properties
• K is too large to iterate (often given as string)
• Property depends on digits, not the number’s value
• Need to track cumulative properties (sum, product, count of specific digits)

Don’t Use When:

• K is small enough to iterate directly (K < 10^6)
• Property depends on number theory (use math instead)
• Looking for specific numbers, not counting them

Pattern Recognition Checklist:

• Is K given as a string (large number)? -> Consider digit DP
• Does the problem ask “count numbers with property X”? -> Digit DP likely
• Can the property be computed digit by digit? -> Digit DP applicable
• Is the property about digit sum/product/pattern? -> Classic digit DP

Related Problems

Easier (Do These First)

Similar Difficulty

Harder (Do These After)

Key Takeaways

1. The Core Idea: Build numbers digit by digit, using DP to count valid configurations
2. State Design: (position, is_tight, accumulated_property) covers most digit DP problems
3. Tight Constraint: Critical for ensuring we only count numbers <= K
4. Pattern: Digit DP is essential for counting problems with large numeric bounds

Practice Checklist

Before moving on, make sure you can:

• Explain what “tight” means and how it transitions
• Identify digit DP problems by their characteristics
• Implement the basic digit DP template from memory
• Extend this pattern to other digit properties (count of 7s, alternating digits, etc.)

Additional Resources

• AtCoder DP Contest - Educational DP problem set
• CP-Algorithms: Digit DP
• CSES Counting Numbers - Digit DP application