Number of Digit One
Problem Description
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
Example 1:
Input: n = 13
Output: 6
Example 2:
Input: n = 0
Output: 0
Constraints:
0 <= n <= 109
Solve it on LeetCode
Approaches
1. Brute Force
This basic solution involves iterating through each number from 1 to n and counting the number of times the digit 1 appears. Though simple, this approach lacks efficiency.
Intuition:
For each number, convert it to a string and count the occurrences of '1'. Sum the counts across all numbers.
Code:
- Time Complexity: O(n * log_{10}(n))) — We check each number and its digits.
- Space Complexity: O(1) — Constant space is used.
2. Mathematical Solution
While the brute-force solution checks each number individually, an optimal approach models a mathematical pattern based on the position of each digit.
Intuition:
Consider how many 1s appear at each digit through the entire sequence from 0 to n. By calculating the contribution of 1s for units, tens, hundreds places independently, a more efficient solution is derived.
For each digit in the number, split the number into three parts: higher, current, and lower part. Compute possible occurrences of 1 considering each position as the current digit.
Code:
- Time Complexity: O(log_{10}(n)) — The number of iterations is based on the number of digits in
n. - Space Complexity: O(1) — Only a few variables are used.