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
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 ; } }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.