Count of Integers

Count of Integers

What is this problem about?

This "Hard" problem asks you to count how many integers $x$ exist such that $num1 \le x \le num2$ and the sum of the digits of $x$ is between min_sum and max_sum inclusive. $num1$ and $num2$ are given as strings because they can be very large (up to 100 digits).

Why is this asked in interviews?

Cisco and Goldman Sachs use this to test a candidate's mastery of Digit Dynamic Programming. Because the numbers are too large to be represented as standard integers, any simulation or iterative approach is impossible. This problem requires you to build numbers digit by digit while satisfying boundary constraints and sum constraints.

Algorithmic pattern used

The pattern is Digit Dynamic Programming (Digit DP).

1. Use the prefix property: Result = Count(num2) - Count(num1 - 1).
2. Define a recursive function dp(index, current_sum, is_less, is_started):
   • index: Current digit position being filled.
   • current_sum: Sum of digits selected so far.
   • is_less: Boolean flag indicating if the number being built is already strictly less than the prefix of the bound.
3. Use memoization to store results for these states.

Example explanation

$num2 = "20", min\_sum = 1, max\_sum = 2$.

• Build 2-digit numbers:
  • Position 0: Can pick 0, 1, 2.
  • If pick 1 at pos 0: current_sum = 1. At pos 1, can pick 0 (sum 1), 1 (sum 2). Numbers: 10, 11.
  • If pick 2 at pos 0: current_sum = 2. At pos 1, can only pick 0 (sum 2). Number: 20.
  • If pick 0 at pos 0: ... numbers 1, 2.
• Total valid: 1, 2, 10, 11, 20.

Common mistakes candidates make

The most common mistake is failing to handle the "num1 - 1" string subtraction correctly, especially when $num1$ is a power of 10 (like 1000). Another mistake is not including enough states in the DP (like the is_less constraint), leading to counts that exceed the bound $num2$.

Interview preparation tip

Digit DP is a high-level technique. If you see a range problem where the numbers are given as strings, it is almost 100% a Digit DP problem. Practice the standard template until you can write the index and is_less transitions without hesitation.