Number of Digit One

HARD

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 <= 10⁹

Approaches

Checkout 2 different approaches to solve Number of Digit One. Click on different approaches to view the approach and algorithm in detail.

Brute Force Approach

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

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 Analysis

Time Complexity: O(n * log n) - where n is the input number and log n is for converting each number to string and counting 1'sSpace Complexity: O(log n) - space needed to store the string representation of numbers

Pros and Cons

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

Code Solutions

Checking out 4 solutions in different languages for Number of Digit One. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Number of Digit One

Patterns:

MathRecursionDynamic Programming

Companies:

Atlassian |Google |