1067. Digit Count in Range

Problem Description

Given a single-digit integer d and two integers low and high, you need to compute how often the digit d appears within the range of numbers from low to high inclusively. It involves counting occurrences of d in each number and summing them up for that entire range. For instance, if d is 3 and the range is from 10 to 13, then d appears 2 times (once in "13" and once in "3").

Intuition

To solve this problem efficiently, rather than iterating over each number in the range and counting occurrences of d (which could be time-consuming for large ranges), we apply a digit dynamic programming (DP) strategy with depth-first search (DFS).

The intuition is that the occurrence of digit d in positions of numbers follows certain patterns that can be recursively calculated. For a given number, each of its digits can impact the count differently depending on its place. A digit in the tens place contributes differently to the total count than a digit in the units place, and so on.

The digitsCount method sets up the process by calculating the occurrences of d up to high and subtracting the occurrences up to one less than low to account for the inclusivity of both low and high.

In the f helper function, we:

Initialize an array a to store the digits of the current number n.
Recursively define the dfs function to explore all possible numbers that can be constructed by choosing each digit at a time from the highest to the lowest significant position.
Use parameters pos, cnt, lead, and limit within dfs to track the current position in the number, the count of occurrences of d, whether we are leading with zeros (important for numbers that start with zero when initially factored into the search), and a flag indicating if we are at the limit of our original number n.
Cache the results of dfs using the @cache decorator to avoid recalculating outcomes for the same input parameters, thus optimizing the process.
The recursion trickles down to the base case of pos <= 0 where it returns the cnt of d.
The loop within dfs iterates through all possible digits at the current position, adding to the count when the digit is equal to d and continuing the exploration. The limit helps us to ensure that we do not surpass the original number n we are investigating.

Through this recursive exploration and caching, the solution reduces the overhead that a naive approach would involve and provides the overall count of digit d's occurrences between low and high rapidly.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

In implementing the solution, we take advantage of several algorithmic concepts and Python features like recursion, dynamic programming, memoization, and the modulo operation for dealing with digits of integers. Below is the breakdown of the solution approach:

Class and Method Definition: We define a class Solution with the method digitsCount, which takes the digit d and the range defined by low and high.
Subtraction Trick: The method digitsCount essentially calculates the occurrences of d from 1 to high and subtracts the occurrences of d from 1 to low - 1. This subtraction gives us the precise count within the inclusive range [low, high].
Auxiliary Function f: A helper function f is defined to calculate the number of times d appears up to a given number n. This function is the heart of the digit dynamic programming algorithm.
Digital Analysis via Recursion: We perform a digital analysis where a number n is broken down into its individual digits, and the count of d is obtained for each digit's place using a recursive function dfs.
Cache Decorator: To avoid recomputations of the same states, we use Python's @cache decorator from the functools module for memoization, which automatically handles the storage and retrieval of the results of intermediary recursive calls, making our solution much faster and efficient.
Recursive DFS Function: Within dfs, several parameters are used to guide the recursive search:
- pos represents the current digit position we are analyzing.
- cnt keeps a running total of how many times d has been encountered.
- lead is a boolean indicating whether the current series of digits has leading zeros.
- limit is a boolean that checks if the current series of digits is limited by the digit of n at the same position.
Exploration of Digits: For each digit position, we try all possible values from 0 to 9 (or up to the digit in n if it is the most significant digit and we are at the limit). This is done by looping through and making recursive calls to dfs. We update the running cnt when the digit being placed is d.
Base Case: When pos is 0, we have analyzed all digit positions of the number, and thus we return the current count cnt.
Digit Array a: To capture the individual digits of n, we form an array a, where a[l] is the digit at the lth position from the right, with l being incremented as we divide n by 10.

This solution is a typical DFS digit DP where we explore each digit's placement, taking care to not exceed the maximal limit which the given number n sets. The correctness comes from the fact that every number from 1 to n is either explored or counted recursively, and we sum those that contain the digit d.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using a small example with d = 1, low = 10, and high = 15. We are to count how often the digit 1 appears within the range from 10 to 15.

Class and Method Invocation: We instantiate our Solution class and call the method digitsCount(1, 10, 15).
Subtraction Trick: The method digitsCount will compute the occurrences of digit 1 from 1 to 15 and subtract the occurrences of digit 1 from 1 to 9 (i.e., one less than low).
Auxiliary Function f Calls: f(15) and f(9) will be invoked. Let's focus on f(15). A similar process will apply to f(9) and the results will be subtracted from f(15).
Digital Analysis via Recursion:
- Break down the number 15 into its digits and store them in array a ([5, 1]).
- We will use dfs to count how frequently 1 appears, starting with the most significant digit.
Recursive DFS Function:
- Begin by exploring the tens place (which has the digit 1):
  - pos = 2 (position of the tens place)
  - cnt = 0 (no occurrences of 1 yet)
  - lead = False (since we're not considering leading zeros)
  - limit = True (since we cannot exceed the digit 1 in 15)
- We only have one choice for the tens place, which is 1 because of the limit. Set cnt to 1 to reflect this occurrence of 1.
- Now, explore the ones place:
  - pos = 1 (position of the ones place)
  - cnt from tens place is carried over
  - limit is now True because we are still in line with the max limit (1 in tens and 5 in ones place)
- Iterate from 0 to 5 (the digit at the ones place in our limit, 15):
  - Each non-1 digit (0-4) keeps the cnt the same.
  - Encountering the digit 1, cnt increases by 1.
Base Case: Once pos is 0, we've considered both digits, and cnt is returned, here it would be 2.
Digit Array a: For our number 15, the array a holds [5, 1], where each element corresponds to a digit in 15, starting from the least significant one.

Following these steps, the count of digit 1 from 1 to 15 is calculated. The same process with adjustments is used for f(9), and the results are subtracted. The calculation is f(15) - f(9), which gives us the occurrences of 1 in the range [10, 15].

Considering our range [10, 15] and the digit 1, we have 1 appearing in the numbers 10, 11, 12, 13, 14, and 15. The occurrences are:

10: 1 time
11: 2 times
12 to 15: 1 time each

Adding them up, we have a total of 1 + 2 + 1 + 1 + 1 + 1 = 7 occurrences of the digit 1. This result matches what our method digitsCount would output based on the algorithm described.

Solution Implementation

1from functools import lru_cache
2
3class Solution:
4    def digits_count(self, d: int, low: int, high: int) -> int:
5        # The public method that calculates the number of occurrences of digit 'd'
6        # in the range from 'low' to 'high'.
7        return self._count_to_n(high, d) - self._count_to_n(low - 1, d)
8
9    def _count_to_n(self, n, d):
10        # The private method that counts how many times digit 'd' occurs up to number 'n'.
11      
12        @lru_cache(None)
13        def _dfs(pos, count, is_lead, is_limit):
14            # Helper method that uses Depth-First Search (DFS) to count digits.
15            # pos: the current position being considered
16            # count: the total count of 'd' up to the current position
17            # is_lead: a flag to indicate if the current position is leading (can be skipped if leading zero)
18            # is_limit: a flag to indicate if the current number is bounded by 'n'
19
20            # Base case: if the position is less than or equal to 0, we return the count.
21            if pos <= 0:
22                return count
23
24            # Determine the upper bound for the digit we're examining. 
25            # It's the current digit of 'n' if we're still within limits; otherwise, it's 9.
26            upper_bound = digit_array[pos] if is_limit else 9
27            total = 0
28
29            # Iterate through all digit possibilities for this position and recurse
30            for i in range(upper_bound + 1):
31                if i == 0 and is_lead:
32                    # Continue with leading zeros without incrementing the count.
33                    total += _dfs(pos - 1, count, is_lead, is_limit and i == upper_bound)
34                else:
35                    # Recurse to the next position incrementing the count if the digit is 'd'.
36                    total += _dfs(pos - 1, count + (i == d), False, is_limit and i == upper_bound)
37            return total
38
39        # Convert 'n' to an array of digits for easier manipulation
40        digit_array = [0] * 11
41        length = 0
42        while n:
43            length += 1
44            digit_array[length] = n % 10
45            n //= 10
46
47        # Start the DFS from the highest digit position with initial count 0,
48        # setting the is_lead flag to True, and the is_limit flag to True.
49        return _dfs(length, 0, True, True)
50

1class Solution {
2    private int digitToCount; // The digit we're counting occurrences of
3    private int[] numArray = new int[11]; // An array to store the individual digits of the number
4    private int[][] memo = new int[11][11]; // Memoization table for dynamic programming
5
6    // Counts the occurrences of the digit between low and high
7    public int digitsCount(int d, int low, int high) {
8        this.digitToCount = d;
9        return countDigits(high) - countDigits(low - 1);
10    }
11
12    // Helper function to initialize memoization table and calculate digit frequency for n
13    private int countDigits(int n) {
14        for (int[] row : memo) {
15            Arrays.fill(row, -1); // Fill the memoization table with -1 to indicate uncalculated states
16        }
17        int length = 0;
18        // Split the number into its digits and store them in numArray
19        while (n > 0) {
20            numArray[++length] = n % 10;
21            n /= 10;
22        }
23        // Start the depth-first search (DFS) from the most significant digit
24        return dfs(length, 0, true, true);
25    }
26
27    // DFS function to calculate digit frequency
28    private int dfs(int pos, int count, boolean isLeadingZero, boolean isWithinLimit) {
29        if (pos == 0) {
30            return count; // Base case: we've counted all the digits
31        }
32        // If the state has been computed and isn't affected by leading zeros/limit - return the result from memo table
33        if (!isLeadingZero && !isWithinLimit && memo[pos][count] != -1) {
34            return memo[pos][count];
35        }
36        int upperBound = isWithinLimit ? numArray[pos] : 9; // Determine the upper bound for this digit position
37        int sum = 0;
38        // Iterate over possible digits and recurse
39        for (int digit = 0; digit <= upperBound; ++digit) {
40            if (digit == 0 && isLeadingZero) {
41                // Special case for leading zeros - we don't increase count
42                sum += dfs(pos - 1, count, true, isWithinLimit && digit == upperBound);
43            } else {
44                // For non-leading zeros, increase count if the digit matches `digitToCount`
45                sum += dfs(pos - 1, count + (digit == digitToCount ? 1 : 0), false, isWithinLimit && digit == upperBound);
46            }
47        }
48        // Only store the result in the memo table if it's not affected by leading zeros/limit
49        if (!isLeadingZero && !isWithinLimit) {
50            memo[pos][count] = sum;
51        }
52        return sum; // Return the total count calculated
53    }
54}
55

1class Solution {
2public:
3    int targetDigit; // Digit to count
4    int digitsArray[11]; // Array to store digits of the number
5    int memo[11][11]; // DP memoization table
6
7    // Returns the count of digit d in the range [low, high]
8    int digitsCount(int d, int low, int high) {
9        targetDigit = d;
10        // Subtract the count of target digits up to (low - 1) from the count up to high
11        return countUpTo(high) - countUpTo(low - 1);
12    }
13
14    // Preprocess the number and initiates the DFS for counting
15    int countUpTo(int n) {
16        memset(memo, -1, sizeof memo);
17        int length = 0;
18        // Extract and store each digit of n into digitsArray
19        while (n) {
20            digitsArray[++length] = n % 10;
21            n /= 10;
22        }
23        // Begin a depth-first search to count how many times targetDigit appears
24        return dfs(length, 0, true, true);
25    }
26
27    // DFS function to find count of targetDigit
28    int dfs(int pos, int count, bool isLeadingZero, bool isLimit) {
29        // When the current position is 0, return the count of the target digit
30        if (pos <= 0) {
31            return count;
32        }
33        if (!isLeadingZero && !isLimit && memo[pos][count] != -1) {
34            return memo[pos][count];
35        }
36        int upperBound = isLimit ? digitsArray[pos] : 9;
37        int sum = 0;
38        for (int i = 0; i <= upperBound; ++i) {
39            if (i == 0 && isLeadingZero) {
40                // Skip the leading zero and continue the DFS
41                sum += dfs(pos - 1, count, isLeadingZero, isLimit && i == upperBound);
42            } else {
43                // Increment the count if the current digit is equal to targetDigit
44                sum += dfs(pos - 1, count + (i == targetDigit), false, isLimit && i == upperBound);
45            }
46        }
47        // Store the result in memo if there is no leading zero and no limit constraint
48        if (!isLeadingZero && !isLimit) {
49            memo[pos][count] = sum;
50        }
51        return sum;
52    }
53};
54

1// Global variables
2let targetDigit: number; // Digit to count
3let digitsArray: number[] = new Array(11); // Array to store digits of the number, initialized to length 11
4let memo: number[][] = Array.from(Array(11), () => new Array(11).fill(-1)); // DP memoization table filled with -1
5
6// Returns the count of digit 'd' in the range [low, high]
7function digitsCount(d: number, low: number, high: number): number {
8  targetDigit = d;
9  // Subtract the count of target digits up to (low - 1) from the count up to high
10  return countUpTo(high) - countUpTo(low - 1);
11}
12
13// Preprocess the number and initiates the DFS for counting
14function countUpTo(n: number): number {
15  memo.forEach(row => row.fill(-1)); // Reset memoization table
16  let length = 0;
17  // Extract and store each digit of n into digitsArray
18  while (n > 0) {
19    digitsArray[++length] = n % 10;
20    n = Math.floor(n / 10);
21  }
22  // Begin a depth-first search to count how many times targetDigit appears
23  return dfs(length, 0, true, true);
24}
25
26// DFS function to find the count of targetDigit
27function dfs(pos: number, count: number, isLeadingZero: boolean, isLimit: boolean): number {
28  // When the current position is 0, return the count of the target digit
29  if (pos === 0) {
30    return count;
31  }
32  if (!isLeadingZero && !isLimit && memo[pos][count] !== -1) {
33    return memo[pos][count];
34  }
35  let upperBound = isLimit ? digitsArray[pos] : 9;
36  let sum = 0;
37  for (let i = 0; i <= upperBound; ++i) {
38    if (i === 0 && isLeadingZero) {
39      // Skip the leading zero and continue the DFS
40      sum += dfs(pos - 1, count, isLeadingZero, isLimit && i === upperBound);
41    } else {
42      // Increment the count if the current digit is equal to targetDigit
43      sum += dfs(pos - 1, count + (i === targetDigit ? 1 : 0), false, isLimit && i === upperBound);
44    }
45  }
46  // Store the result in memo if there is no leading zero and no limit constraint
47  if (!isLeadingZero && !isLimit) {
48    memo[pos][count] = sum;
49  }
50  return sum;
51}
52
53// Sample usage (Uncomment lines below to test)
54// console.log(digitsCount(1, 1, 13)); // Count of digit 1 in the range [1, 13]
55

Time and Space Complexity

The provided code snippet defines a digitsCount function that counts how many times a digit d appears in the range between two numbers low and high (inclusive) by leveraging a helper function f. The f function uses a depth-first search (DFS) method dfs to calculate the digit count up to a given number n, and the digit appearance is cached for efficiency. Here is the analysis of its complexity:

Time Complexity:

The main factor in determining the time complexity is the DFS function, which has memoization provided by the cache decorator. The DFS explores the positional digit paths, with each position having up to 10 possible digits to consider (0-9). However, due to memoization, calculations for each unique (pos, cnt, lead, limit) state do not repeat. The maximum value of pos is log10(n), which is the number of digits in n.

The DFS function is called at most 10 * log10(n) times for unique states, because cnt can only be at most log10(n) (in a case where all digits are d), and both lead and limit have 2 states each (True or False).

Therefore, the total number of unique states is O(log10(n)^2 * 2 * 2) = O((log(n))^2). For each state, the time to process is constant. Thus, the time complexity of the dfs function is O((log(n))^2).

Since the digitsCount function runs f twice, once for high and once for low, the overall time complexity of digitsCount is also O((log(n))^2) where n is the maximum of low and high.

Space Complexity:

For space complexity, we need to account for the stack space used by the DFS function (in the case of no memoization) and the space used by memoization to store intermediate results. The maximum depth of the recursive DFS call is bound by the number of digits in n (log10(n)). Memoization will store each unique state achieved during execution. Therefore, the space needed for memoization will also be O((log(n))^2) as discussed in the time complexity analysis.

Consequently, the space complexity of the algorithm is determined by the memoization, which is O((log(n))^2).

In summary, both the time complexity and space complexity of the provided Solution class are O((log(n))^2).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological Sort

Uniform Cost Search

Monotonic Stack

Memoization

I don’t know