233. Number of Digit One

Problem Description

The problem statement is asking us to calculate the total count of the digit 1 in the range of all non-negative integers less than or equal to a given integer n. In other words, if n is 13, for instance, we should count how many times the digit 1 appears in the following sequence of numbers: 0, 1, 2, 3, ..., 13. This would include occurrences of 1 in numbers like 10, 11, 12, and 13, not just the single occurrence in the number 1.

Intuition

The intuitive approach for this problem might involve iterating through all the numbers from 0 to n and count the digit 1 in each number. However, such a method would not be efficient for larger values of n.

The solution provided leverages a method known as "Digital Dynamic Programming" (Digital DP). This approach optimizes the counting process by breaking it down into a digit-by-digit examination, considering the recurrence and patterns of ones appearing in each positional digit.

The process is as follows:

Reverse engineer the number n to obtain a digit array a, which stores the digits of n in reverse order. For instance, if n is 213, a will be [3,1,2].
We define a recursive function dfs(pos, cnt, limit) where pos indicates the current position we're checking in a, cnt counts the number of ones we've found so far, and limit is a flag indicating if we've reached the upper limit (the original number n).
The base condition of the recursive function is when pos <= 0, meaning we've checked all positions and we return the count of 1s (cnt).
For each recursive call, if limited by n (limit is true), we use the digit in a[pos] as our upper bound. This represents counting up to the current digit in the original number n. If not limited, we can go up to 9 (all possibilities for a decimal digit).
The recursive calls iterate from 0 up to the upper bound, incrementing cnt if the current digit is 1 and proceeding to the next position to the left (pos - 1).
A dynamic programming optimization is applied by caching the results of the recursive calls. This ensures that each distinct state (pos, cnt, limit) is computed only once, further improving efficiency.

In essence, this Digital DP solution breaks down the large problem into smaller subproblems and caches the solutions to these subproblems to avoid redundant calculations, resulting in more optimal time complexity compared to simple iterative counting.

Learn more about Recursion, Math and Dynamic Programming patterns.

Solution Approach

The solution approach for the problem utilizes a recursive algorithm with memoization (a dynamic programming technique) to efficiently compute the count of digit 1 in the given range. Let's walk step-by-step through the implementation details:

Algorithm

Digit Array Preparation:
- The input integer n is broken down into its constituent digits and stored in reverse order in an array a. This reversal puts the least significant digit at a[1] and progresses towards the most significant digit. This is convenient for our recursive function, which will build the count from the least significant digit upward.
Recursive Function (Dynamic Programming):
- The core of the solution is a recursive function dfs(pos, cnt, limit) which is defined within the class. It carries the current position pos in the array a, the current count cnt of ones, and a boolean limit that determines whether the current path is limited by the original number's digits.
Base Condition:
- When pos is 0, the recursion returns cnt, which means no more digits are left to process, so we've counted all occurrences of 1.
Building Count and Recursing:
- The recursive function spans across all possible digits from 0 up to a[pos] if limit is True, or up to 9 if limit is False. For each digit, the function calls itself with pos - 1, and incrementing count if the current digit is 1, passing on the limit if we are still within the bounds of the original number.

Memoization

Memoization is achieved via the @cache decorator from the functools module (in Python 3.9+). This caches the results based on the arguments of the recursive function to avoid redundant calculations.

Data Structures and Patterns

Digit Array: An array a is used to hold the individual digits of the number in reverse order.
Caching: The @cache decorator on top of the recursive function implicitly creates a dictionary (or similar data structure) where each unique state (combinations of pos, cnt, and limit) is stored alongside the computed result.
Digital Dynamic Programming (Digital DP): This pattern involves dissecting a numerical problem into digital-level subproblems, and solving them using the principles of dynamic programming, allowing overlap and reuse of subproblem solutions.

The Solution class applies this algorithm by first initializing the digit array a and calling the dfs function with the starting parameters, resulting in the final count of the digit 1 in all numbers less than or equal to n.

This approach is significantly more efficient for larger numbers compared to a brute force method, as it avoids counting digit by digit through all numbers and leverages subproblem solutions.

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 assume we have n = 23. We want to calculate the total count of the digit 1 in the range of all non-negative integers less than or equal to n.

Digit Array Preparation:
- First, we break down 23 into its constituent digits 2 and 3 and reverse their order to get the digit array a = [3, 2].
Recursive Function Initialization:
- We initialize our recursive function dfs(pos, cnt, limit) and start at the most significant position (in a, the starting position pos is the length of the array a), with a cnt of 0 because we haven't counted any 1's yet, and with the limit boolean set to True because we can’t exceed the number n.
Initial Recursive Call:
- We call dfs(2, 0, True) corresponding to the most significant digit (2 in number 23), with a count of 0 and limit as True.
Recursive Calls and Count Building:
- dfs(2, 0, True)
  - It iterates through digits from 0 to 2 (since limit is True and a[2] is 2).
  - Calls dfs(1, 0, True) for 0
  - Calls dfs(1, 0, True) for 1 (found one '1', so cnt will increase by 1)
  - Calls dfs(1, cnt, True) for 2 (limit remains True for 2 because it’s equal to a[2])
- dfs(1, cnt, True)
  - This will iterate from 0 to 3 (since limit is True and a[1] is 3).
  - Calls dfs(0, cnt, True) for 0
  - Calls dfs(0, cnt, True) for 1 (found one '1', so cnt will increase by 1)
  - Calls dfs(0, cnt, True) for 2
  - Calls dfs(0, cnt, True) for 3 (limit is now False for 3 because it’s not equal to a[1])
Base Condition and Count Accumulation:
- dfs(0, cnt, limit) will hit the base condition pos == 0, and return the cnt which is the count of ones accumulated from the recursive calls.
Memoization:
- Through these recursive calls, if we encounter the same pos, cnt, and limit state, the @cache decorated dfs function will use the stored result instead of recomputing it.
Counting Ones:
- From the iteration on dfs(1, 0, True), we have found '1' at the second position only once in the numbers from 0-9 (i.e., 1, since every other number from 10-19 is outside our limit, it is counted only once).
- From the iteration on dfs(1, 1, True), when the first digit is '1', we add the instances, we get the numbers 10, 11, 12, 13 (which counts for another 1), 14, 15, 16, 17, 18, 19 – where '1' occurs ten times due to the second digit ranging from 0-9.

By summing these up, we get a total count of the digit '1' in the range of all non-negative integers less than or equal to n = 23, which is 13 times. This involves counting the singular '1's in the range 1-9, the tens digit '1' in the range 10-19, and the one's digit '1' in 21.

Solution Implementation

1from functools import lru_cache
2
3class Solution:
4    def countDigitOne(self, n: int) -> int:
5        # Use lru_cache decorator to memoize the results of the recursive calls
6        @lru_cache(maxsize=None)
7        def dfs(position, count_ones, is_limit):
8            # Base case: if no more digits to process, return the count of ones found
9            if position == 0:
10                return count_ones
11            # Determine the upper bound for the current digit.
12            # If is_limit is True, the upper bound is the current digit in the number.
13            # Otherwise, it is 9 (the maximum value for a digit).
14            upper_bound = digits[position] if is_limit else 9
15          
16            # Initialize the answer for this position
17            ans = 0
18            # Iterate over all possible digits for this position
19            for digit in range(upper_bound + 1):
20                # Calculate the answer recursively. Increase the count if the current digit is 1.
21                # Limit flag is carried over and set to True if we reached the upper_bound.
22                ans += dfs(position - 1, count_ones + (digit == 1), is_limit and digit == upper_bound)
23            return ans
24
25        # Convert the number to a list of its digits, reversed.
26        digits = [0] * 12
27        length = 0
28        while n:
29            digits[length + 1] = n % 10  # Store the digit
30            n //= 10                     # Move to the next digit
31            length += 1
32      
33        # Invoke the recursive DFS function starting with the most significant digit
34        return dfs(length, 0, True)
35

1public class Solution {
2
3    // The 'a' array holds the digits of the number in reverse order.
4    private int[] digits = new int[12];
5
6    // The 'dp' array memoizes results for dynamic programming approach.
7    private int[][] memo = new int[12][12];
8
9    // This method counts the number of digit '1's in numbers from 1 to 'n'.
10    public int countDigitOne(int n) {
11        int length = 0;
12
13        // Split the integer 'n' into its digits.
14        while (n > 0) {
15            digits[++length] = n % 10;
16            n /= 10;
17        }
18
19        // Initialize memoization array with -1 to represent uncalculated states.
20        for (int[] row : memo) {
21            Arrays.fill(row, -1);
22        }
23
24        // Start the depth-first search from the most significant digit.
25        return dfs(length, 0, true);
26    }
27
28    // Perform a depth-first search.
29    private int dfs(int position, int countOfOnes, boolean isLimited) {
30        // If we have processed all the digits, return the count of '1's.
31        if (position <= 0) {
32            return countOfOnes;
33        }
34
35        // If we are not limited by the most significant digit and we have computed this state before, return the memoized result.
36        if (!isLimited && memo[position][countOfOnes] != -1) {
37            return memo[position][countOfOnes];
38        }
39
40        // Determine the upper bound of the current digit we can place.
41        int upperBound = isLimited ? digits[position] : 9;
42        int sum = 0;
43
44        // Try all possible digits at the current position.
45        for (int digit = 0; digit <= upperBound; ++digit) {
46            // Accumulate results from deeper levels, adjusting the count of '1's and the limit flag.
47            sum += dfs(position - 1, countOfOnes + (digit == 1 ? 1 : 0), isLimited && digit == upperBound);
48        }
49
50        // If we are not limited, memoize the result for the current state.
51        if (!isLimited) {
52            memo[position][countOfOnes] = sum;
53        }
54
55        // Return the calculated sum for the current state.
56        return sum;
57    }
58
59    // Helper method to fill the 'dp' array with a value.
60    private static void fillDp(int[][] dp, int value) {
61        for (int[] row : dp) {
62            Arrays.fill(row, value);
63        }
64    }
65}
66

1class Solution {
2public:
3    int digits[12];
4    int memo[12][12];
5
6    // This method calculates the number of digit '1's that appear when counting from 1 to the given number n.
7    int countDigitOne(int n) {
8        int length = 0; // Initialize the length to store the number of digits in n.
9        // Store the digits of n in reverse order.
10        while (n) {
11            digits[++length] = n % 10; // Store the last digit of n.
12            n /= 10; // Remove the last digit from n.
13        }
14        memset(memo, -1, sizeof memo); // Initialize the memoization array to -1.
15        return dfs(length, 0, true); // Start the DFS from the most significant digit.
16    }
17
18    // This method uses depth-first search to count the number of occurrences of the digit '1'.
19    int dfs(int pos, int count, bool limit) {
20        if (pos <= 0) {
21            return count; // Base case: If all positions are traversed, return the count of '1's.
22        }
23        if (!limit && memo[pos][count] != -1) {
24            return memo[pos][count]; // If we are not at the limit and we have a memoized result, return it.
25        }
26        int ans = 0; // Initialize the answer for the current recursion level.
27        int upperBound = limit ? digits[pos] : 9; // Determine the upper bound for the current digit.
28        // Enumerate possibilities for the current digit.
29        for (int i = 0; i <= upperBound; ++i) {
30            // Calculate the count of '1's for the next position, updating count if the current digit is '1'.
31            ans += dfs(pos - 1, count + (i == 1), limit && i == upperBound);
32        }
33        if (!limit) {
34            memo[pos][count] = ans; // If not at the limit, memoize the result.
35        }
36        return ans; // Return the computed answer for the current digit position.
37    }
38};
39

1let digits: number[] = Array(12).fill(0);
2let memo: number[][] = Array.from(Array(12), () => Array(12).fill(-1));
3
4// This function calculates the number of digit '1's that appear when counting from 1 to the given number n.
5function countDigitOne(n: number): number {
6    let length = 0; // Initialize the length to store the number of digits in n.
7    // Store the digits of n in reverse order.
8    while (n > 0) {
9        digits[++length] = n % 10; // Store the last digit of n.
10        n = Math.floor(n / 10); // Remove the last digit from n.
11    }
12    // Reset the memoization array to -1 for each new computation.
13    memo = Array.from(Array(12), () => Array(12).fill(-1));
14    return dfs(length, 0, true); // Start the depth-first search from the most significant digit.
15}
16
17// This function uses depth-first search to count the number of occurrences of the digit '1'.
18function dfs(pos: number, count: number, limit: boolean): number {
19    if (pos <= 0) {
20        return count; // Base case: If all positions are traversed, return the count of '1's.
21    }
22    if (!limit && memo[pos][count] !== -1) {
23        return memo[pos][count]; // If we are not at the limit and we have a memoized result, return it.
24    }
25    let ans = 0; // Initialize the answer for the current recursion level.
26    let upperBound = limit ? digits[pos] : 9; // Determine the upper bound for the current digit.
27    // Enumerate possibilities for the current digit.
28    for (let i = 0; i <= upperBound; ++i) {
29        // Calculate the count of '1's for the next position, updating count if the current digit is '1'.
30        ans += dfs(pos - 1, count + (i === 1 ? 1 : 0), limit && i === upperBound);
31    }
32    if (!limit) {
33        memo[pos][count] = ans; // If not at the limit, memoize the result.
34    }
35    return ans; // Return the computed answer for the current digit position.
36}
37

Time and Space Complexity

Time Complexity

The time complexity of the given Python code involves analyzing the depth-first search (dfs) function. The dfs function is called recursively with several key conditions that impact its running time:

The recursion depth is determined by the parameter pos, which can be as large as the number of digits in n. Let's denote the number of digits in n as d.
For each call to dfs, there is a loop that iterates at most 10 times (digits 0 through 9), represented by the variable up.
The function uses memoization via the @cache decorator, significantly reducing the number of calculations by caching and reusing results of previous computations.

Considering these points, the time complexity can be approximated by O(d * 10 * d), since dfs will be called for d levels, and at each level, it will iterate through up to 10 possibilities, and the work done at each level is O(d) to handle the limiting cases where limit is True. Memoization ensures that results for each unique combination of (pos, cnt, limit) are not recomputed, which might otherwise lead to an exponential time complexity of O(10^d).

Hence, with memoization, the final time complexity is O(d^2 * 10).

Space Complexity

The space complexity comprises the space used by the recursive call stack and the space required to store the memoized results:

The recursion can go as deep as d, representing the space used by the call stack.
The @cache decorator uses space to store results of unique combinations of arguments to the dfs function. The number of unique argument combinations can be up to d * 2 * d, since pos can take up to d values, cnt can take up to d values (as it counts the number of 1s and there are at most d ones), and limit can be either True or False.

Thus, the space complexity is O(d^2) for the memoization and the call stack together.

Overall, the space complexity can be represented as O(d^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

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know