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 numbern
. - 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
, andlimit
withindfs
to track the current position in the number, the count of occurrences ofd
, 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 numbern
. - 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 thecnt
ofd
. - The loop within
dfs
iterates through all possible digits at the current position, adding to the count when the digit is equal tod
and continuing the exploration. Thelimit
helps us to ensure that we do not surpass the original numbern
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 methoddigitsCount
, which takes the digitd
and the range defined bylow
andhigh
. -
Subtraction Trick: The method
digitsCount
essentially calculates the occurrences ofd
from 1 tohigh
and subtracts the occurrences ofd
from 1 tolow - 1
. This subtraction gives us the precise count within the inclusive range[low, high]
. -
Auxiliary Function
f
: A helper functionf
is defined to calculate the number of timesd
appears up to a given numbern
. 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 ofd
is obtained for each digit's place using a recursive functiondfs
. -
Cache Decorator: To avoid recomputations of the same states, we use Python's
@cache
decorator from thefunctools
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 timesd
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 ofn
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 todfs
. We update the runningcnt
when the digit being placed isd
. -
Base Case: When
pos
is 0, we have analyzed all digit positions of the number, and thus we return the current countcnt
. -
Digit Array
a
: To capture the individual digits ofn
, we form an arraya
, wherea[l]
is the digit at thel
th position from the right, withl
being incremented as we dividen
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 EvaluatorExample 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 methoddigitsCount(1, 10, 15)
. -
Subtraction Trick: The method
digitsCount
will compute the occurrences of digit1
from1
to15
and subtract the occurrences of digit1
from1
to9
(i.e., one less thanlow
). -
Auxiliary Function
f
Calls:f(15)
andf(9)
will be invoked. Let's focus onf(15)
. A similar process will apply tof(9)
and the results will be subtracted fromf(15)
. -
Digital Analysis via Recursion:
- Break down the number
15
into its digits and store them in arraya
([5, 1]
). - We will use
dfs
to count how frequently1
appears, starting with the most significant digit.
- Break down the number
-
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 of1
yet)lead
=False
(since we're not considering leading zeros)limit
=True
(since we cannot exceed the digit1
in15
)
- We only have one choice for the tens place, which is
1
because of thelimit
. Setcnt
to 1 to reflect this occurrence of1
. - Now, explore the ones place:
pos
= 1 (position of the ones place)cnt
from tens place is carried overlimit
is nowTrue
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 thecnt
the same. - Encountering the digit
1
,cnt
increases by 1.
- Each non-
- Begin by exploring the tens place (which has the digit
-
Base Case: Once
pos
is 0, we've considered both digits, andcnt
is returned, here it would be 2. -
Digit Array
a
: For our number15
, the arraya
holds[5, 1]
, where each element corresponds to a digit in15
, 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 time11
: 2 times12
to15
: 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.
Is the following code DFS or BFS?
1void search(Node root) { 2 if (!root) return; 3 visit(root); 4 root.visited = true; 5 for (Node node in root.adjacent) { 6 if (!node.visited) { 7 search(node); 8 } 9 } 10}
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.