Number of Digit One - Practice Coding Problems

Number of Digit One - Problem

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example, if n = 13, the numbers are: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13. The digit 1 appears in: 1, 10, 11, 12, 13. Counting each occurrence: 1 appears 1 time, 10 has 1 occurrence, 11 has 2 occurrences, 12 has 1 occurrence, and 13 has 1 occurrence. Total = 6.

Input & Output

Example 1 — Small Number

$ Input: n = 13

› Output: 6

💡 Note: Numbers 0-13: digit 1 appears in 1(×1), 10(×1), 11(×2), 12(×1), 13(×1) = total 6 times

Example 2 — Single Digit

$ Input: n = 9

› Output: 1

💡 Note: Numbers 0-9: digit 1 appears only in number 1, so total is 1

Example 3 — Larger Number

$ Input: n = 99

› Output: 20

💡 Note: Units place: 1,11,21,31,41,51,61,71,81,91 (10 ones). Tens place: 10-19 (10 ones). Total: 20

Constraints

0 ≤ n ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Range

Given n=13, check numbers 0,1,2,...,13

Count 1s

Find all occurrences of digit 1

Output Total

Return total count of 1s

Key Takeaway

🎯 Key Insight: Use mathematical patterns to count 1s by digit position instead of checking every number

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The mathematical approach is optimal by analyzing digit patterns instead of checking every number. Key insight: Count 1s by digit position using mathematical formulas. Best approach: O(log n) time, O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Every Number	O(n log n)	O(1)	Iterate through all numbers from 1 to n and count digit 1s
Mathematical Pattern Recognition	O(log n)	O(1)	Count 1s by analyzing digit positions using mathematical patterns

Brute Force - Check Every Number — Algorithm Steps

Iterate through numbers 1 to n
Convert each number to string
Count '1' characters in each string
Sum all counts

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Each Number

Go through 1, 2, 3, ..., n

Count 1s

Count digit 1s in each number

Sum Total

Add all counts together

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        int num = i;
        while (num > 0) {
            if (num % 10 == 1) count++;
            num /= 10;
        }
    }
    return count;
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Loop n times, each iteration processes log n digits

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for counting

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Every Number — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler