LeetCode 1067 - Digit Count in Range

This problem asks us to count how many times a given digit d appears in every integer within a range [low, high]. For instance, if d = 1 and the range is [1, 13], we count all occurrences of the digit 1 in the numbers 1 through 13.

leetcodehardmathdynamic-programming

LeetCode Problem 1067

Difficulty: 🔴 Hard
Topics: Math, Dynamic Programming

Solution

Problem Understanding

This problem asks us to count how many times a given digit d appears in every integer within a range [low, high]. For instance, if d = 1 and the range is [1, 13], we count all occurrences of the digit 1 in the numbers 1 through 13. Numbers like 11 contribute two occurrences, while numbers like 10 and 12 contribute one occurrence each.

The inputs are a single-digit integer d and two integers low and high representing the inclusive range. The output is a single integer, representing the total count of the digit d across all numbers in that range.

Constraints indicate that d is between 0 and 9, and the range [low, high] can go up to 200 million. This suggests that a brute-force approach of iterating through every number and counting digits would be too slow because it could require examining up to 200 million numbers. Important edge cases include when d = 0 (since leading zeros do not count), very small ranges like [1, 1], very large ranges near the upper bound, and cases where low and high are the same.

Approaches

The brute-force approach is straightforward: iterate through each number from low to high, convert it to a string, and count how many times d occurs. This approach is guaranteed to be correct because it literally counts every occurrence, but it is too slow for large ranges, particularly because the range can go up to 2 * 10^8.

The optimal approach leverages digit dynamic programming (digit DP). The key insight is to treat the number as a sequence of digits and count the occurrences of d position by position. We define a recursive function that counts occurrences of d in all numbers less than or equal to a given number x. By computing count(high) and subtracting count(low - 1), we get the total occurrences in [low, high]. This approach avoids iterating through every number individually and reduces the problem to handling digits of numbers, which is logarithmic in the number size.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * log(n)) O(1) Iterate every number and count digits
Optimal (Digit DP) O(log(high)^2) O(log(high)) Count occurrences using digit positions recursively

Algorithm Walkthrough

  1. Convert the number x to a string to work with its digits individually.
  2. Define a recursive helper function countDigits(pos, tight, countSoFar) where pos represents the current digit position, tight indicates if we are limited by the current digit of x, and countSoFar tracks occurrences of d.
  3. At each position, iterate over all possible digits that can appear at that position. If tight is true, the digit cannot exceed the corresponding digit in x.
  4. For each possible digit, recursively compute the number of times d occurs in the remaining positions. Increment countSoFar if the current digit equals d.
  5. Memoize the results of the recursive function to avoid recomputation of the same states.
  6. Finally, compute count(high) - count(low - 1) to get the occurrences of d in the inclusive range [low, high].

Why it works: By breaking the problem down digit by digit and carefully considering the tight constraint, this approach ensures that all numbers are counted exactly once and that digit occurrences are accumulated correctly. Memoization ensures that repeated subproblems are computed only once, which improves efficiency.

Python Solution

class Solution:
    def digitsCount(self, d: int, low: int, high: int) -> int:
        def countUpTo(x: int) -> int:
            s = str(x)
            n = len(s)
            
            from functools import lru_cache
            
            @lru_cache(None)
            def dfs(pos: int, tight: bool, countSoFar: int) -> int:
                if pos == n:
                    return countSoFar
                limit = int(s[pos]) if tight else 9
                total = 0
                for digit in range(0, limit + 1):
                    newTight = tight and (digit == limit)
                    total += dfs(pos + 1, newTight, countSoFar + (digit == d))
                return total
            
            return dfs(0, True, 0)
        
        return countUpTo(high) - countUpTo(low - 1)

The implementation defines a helper function countUpTo which computes the total occurrences of d from 0 up to a given number. Inside, we use a recursive DFS with memoization to traverse each digit position while respecting the "tight" constraint. The recursion counts occurrences at each position, and memoization ensures we do not recompute states. Finally, the answer is obtained by subtracting count(low-1) from count(high) to get the result for the inclusive range [low, high].

Go Solution

func digitsCount(d int, low int, high int) int {
    var countUpTo func(x int) int
    countUpTo = func(x int) int {
        s := fmt.Sprintf("%d", x)
        n := len(s)
        memo := make([][]map[int]int, n)
        for i := range memo {
            memo[i] = make([]map[int]int, 2)
            memo[i][0] = make(map[int]int)
            memo[i][1] = make(map[int]int)
        }
        
        var dfs func(pos int, tight int, countSoFar int) int
        dfs = func(pos int, tight int, countSoFar int) int {
            if pos == n {
                return countSoFar
            }
            if val, ok := memo[pos][tight][countSoFar]; ok {
                return val
            }
            limit := 9
            if tight == 1 {
                limit = int(s[pos] - '0')
            }
            total := 0
            for digit := 0; digit <= limit; digit++ {
                newTight := 0
                if tight == 1 && digit == limit {
                    newTight = 1
                }
                add := 0
                if digit == d {
                    add = 1
                }
                total += dfs(pos+1, newTight, countSoFar+add)
            }
            memo[pos][tight][countSoFar] = total
            return total
        }
        
        return dfs(0, 1, 0)
    }
    
    return countUpTo(high) - countUpTo(low-1)
}

In Go, the recursive function dfs is similar to Python, but memoization is implemented with nested maps to handle the tuple of state (pos, tight, countSoFar). Strings are used to access digits, and integer arithmetic tracks the tight constraint and count of d. The overall logic mirrors the Python version closely.

Worked Examples

Example 1: d = 1, low = 1, high = 13

Number Occurrences of 1
1 1
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 1
11 2
12 1
13 1

Total = 6, which matches the output.

Example 2: d = 3, low = 100, high = 250

The algorithm recursively counts digits in hundreds, tens, and units positions and sums occurrences of 3, giving 35.

Complexity Analysis

Measure Complexity Explanation
Time O(log(high)^2) Each digit position (log(high)) is processed with recursion over possible digits (0-9), resulting in roughly log(high)^2 calls.
Space O(log(high)) The recursion depth is the number of digits, and memoization stores results for each state combination, also proportional to number of digits.

The complexity is much better than brute force because we avoid iterating through every number individually. The logarithmic dependency comes from processing digits rather than numbers themselves.

Test Cases

# Provided examples
assert Solution().digitsCount(1, 1, 13) == 6  # example 1
assert Solution().digitsCount(3, 100, 250) == 35  # example 2

# Edge and boundary cases
assert Solution().digitsCount(0, 1, 10) == 1  # only 10 contains 0
assert Solution().digitsCount(9, 9, 9) == 1  # single number equal to d
assert Solution().digitsCount(2, 200000000, 200000000) == 1  # maximum input edge case
assert Solution().digitsCount(5, 1, 100) == 20  # multiple occurrences within small range
Test Why
digitsCount(1, 1, 13) Basic small range, multiple