Number of Digit One
HardPrompt
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: 6Example 2:
Input: n = 0
Output: 0
Constraints:
0 <= n <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
Iterate through all numbers from 1 to n and count the number of 1's in each number.
Algorithm
- Initialize count = 0
- Loop from i = 1 to n
- Convert i to string
- Count '1's in the string
- Add count to total
- Return total count
Walkthrough
For each number from 1 to n:
- Convert the number to string
- Count the occurrences of '1' in the string
- Add the count to total
public int countDigitOne(int n) { int count = 0; for (int i = 1; i <= n; i++) { String num = String.valueOf(i); for (char c : num.toCharArray()) { if (c == '1') { count++; } } } return count;}Complexity
Time
O(n * log n) - where n is the input number and log n is for converting each number to string and counting 1's
Space
O(log n) - space needed to store the string representation of numbers
Trade-offs
Pros
Simple to understand and implement
Works for small inputs
Cons
Very inefficient for large numbers
Time complexity is high
Not suitable for the given constraints
Use mathematical pattern to count number of 1's by analyzing each digit position and calculating contribution of 1's at each position.
Algorithm
- Initialize count = 0
- For each digit position (i = 1, 10, 100, ...)
- Calculate complete groups contribution
- Calculate partial group contribution
- Add to total count
- Return final count
Walkthrough
For each digit position:
- Calculate the contribution of 1's before current digit
- Calculate the contribution of 1's at current digit
- Calculate the contribution of 1's after current digit
public int countDigitOne(int n) { int count = 0; for (long i = 1; i <= n; i *= 10) { long divider = i * 10; count += (n / divider) * i + Math.min(Math.max(n % divider - i + 1, 0L), i); } return count;}For each position i:
- n/divider gives the number of complete groups
- Each complete group contributes i ones
- The remainder (n % divider) determines if there are additional ones
Complexity
Time
O(log n) - we only need to check each digit position
Space
O(1) - only uses a constant amount of extra space
Trade-offs
Pros
Very efficient solution
Works for all input ranges
Handles large numbers effectively
Cons
More complex to understand
Requires understanding of mathematical pattern
Code might be less intuitive
Solutions
Solution
public class Solution { public int CountDigitOne ( int n ) { if ( n <= 0 ) return 0 ; if ( n < 10 ) return 1 ; return CountDigitOne ( n / 10 - 1 ) * 10 + n / 10 + CountDigitOneOfN ( n / 10 ) * ( n % 10 + 1 ) + ( n % 10 >= 1 ? 1 : 0 ); } private int CountDigitOneOfN ( int n ) { var count = 0 ; while ( n > 0 ) { if ( n % 10 == 1 ) ++ count ; n /= 10 ; } return count ; } }class Solution { private int [] a = new int [ 12 ]; private int [][] dp = new int [ 12 ][ 12 ]; public int countDigitOne ( int n ) { int len = 0 ; while ( n > 0 ) { a [++ len ] = n % 10 ; n /= 10 ; } for ( var e : dp ) { Arrays . fill ( e , - 1 ); } return dfs ( len , 0 , true ); } private int dfs ( int pos , int cnt , boolean limit ) { if ( pos <= 0 ) { return cnt ; } if (! limit && dp [ pos ][ cnt ] != - 1 ) { return dp [ pos ][ cnt ]; } int up = limit ? a [ pos ] : 9 ; int ans = 0 ; for ( int i = 0 ; i <= up ; ++ i ) { ans += dfs ( pos - 1 , cnt + ( i == 1 ? 1 : 0 ), limit && i == up ); } if (! limit ) { dp [ pos ][ cnt ] = ans ; } return ans ; } }class Solution {public: int a[12]; int dp[12][12]; int countDigitOne(int n) { int len = 0; while (n) { a[++len] = n % 10; n /= 10; } memset(dp, -1, sizeof dp); return dfs(len, 0, true); } int dfs(int pos, int cnt, bool limit) { if (pos <= 0) { return cnt; } if (!limit && dp[pos][cnt] != -1) { return dp[pos][cnt]; } int ans = 0; int up = limit ? a[pos] : 9; for (int i = 0; i <= up; ++i) { ans += dfs(pos - 1, cnt + (i == 1), limit && i == up); } if (!limit) { dp[pos][cnt] = ans; } return ans; }};class Solution: def countDigitOne(self, n: int) -> int: @ cache def dfs(pos, cnt, limit): if pos <= 0: return cnt up = a[pos] if limit else 9 ans = 0 for i in range(up + 1): ans += dfs(pos - 1, cnt + (i == 1), limit and i == up) return ans a = [0] * 12 l = 1 while n: a[l] = n % 10 n //= 10 l += 1 return dfs(l, 0, True)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.