Skip to content

Counting Numbers

  • Title: Counting Numbers
  • Judge / source: CSES
  • Original URL: https://cses.fi/problemset/task/2220
  • Secondary topics: Previous digit state, Leading zeros, Range counting
  • Difficulty: medium
  • Subtype: Count numbers in a range with no equal adjacent digits
  • Status: solved
  • Solution file: countingnumbers.cpp

Why Practice This

This is one of the best first digit-DP problems because the extra state is tiny and meaningful:

  • tight: are we still matching the upper bound?
  • started: have we placed the first non-leading-zero digit yet?
  • prev: what was the previous real digit?

Once those three ideas click, much larger digit-DP problems feel far less mysterious.

Recognition Cue

Reach for digit DP when:

  • you need to count numbers in a range
  • the property depends on decimal digits, not arithmetic over the whole value
  • a brute-force loop over every number in [a, b] is too large
  • the condition can be checked while building the number left to right

The classic top-level smell is:

  • "count valid numbers in [L, R]"

That is often a signal to compute solve(R) - solve(L - 1).

Problem-Specific Transformation

The statement asks for a range count with a local digit rule: adjacent digits cannot be equal.

The reusable rewrite is:

  • compute solve(x) = valid numbers in [0, x]
  • build the number digit by digit
  • carry only the information that affects the next digit:
  • previous real digit
  • whether the number has started
  • whether the current prefix is still tight to the bound

That turns the original range question into one memoized DFS over digit states, with a final subtraction for [a, b].

Core Idea

Let solve(x) be the number of valid integers in [0, x].

Then the final answer is:

solve(b) - solve(a - 1)

To compute solve(x), process the decimal digits from left to right with a memoized DFS.

State:

dp[pos][prev][started][tight]

where:

  • pos is the current digit position
  • prev is the previous chosen digit, or a sentinel if the number has not started
  • started says whether a non-leading-zero digit has appeared
  • tight says whether the prefix still matches the bound exactly

Transition:

  • choose the next digit d
  • if started is already true and d == prev, skip it
  • otherwise recurse to the next position with updated flags

Leading zeros need special care:

  • while started is false and we place another 0, we still have not chosen any real digit
  • so there is no "adjacent equal digits" violation yet

That is why the started flag matters.

Complexity

  • positions: at most 19
  • previous-digit states: 11 including the sentinel
  • each state tries at most 10 digits

So the total work is tiny, comfortably within limits.

Pitfalls / Judge Notes

  • The answer is solve(b) - solve(a - 1), not solve(b) - solve(a).
  • 0 itself is valid.
  • Leading zeros should not count as repeated adjacent digits.
  • Memoize only states that are independent of the current bound suffix, typically the tight = false states.

Reusable Pattern

  • Topic page: Digit DP
  • Practice ladder: Digit DP ladder
  • Starter template: digit-dp-skeleton.cpp
  • Notebook refresher: DP cheatsheet
  • Carry forward: separate tightness, started-state, and the carried constraint into explicit DP dimensions.
  • This note adds: the digit condition and memo state needed by this exact counting question.

Solutions