Number of Digit One — Hard Problem & Solution

Problem statement

Count the total number of digit 1 characters that appear across all the integers from 1 to n inclusive.

Example 1

Input: n = 13
Output: 6
Explanation: The ones appear in 1, 10, 11 (twice), 12 and 13.

Example 2

Input: n = 0
Output: 0

Example 3

Input: n = 100
Output: 21

Constraints

• 0 <= n <= 1000000000

How to solve Number of Digit One

Fix a digit position p (1, 10, 100, …) and count how many integers in [1, n] carry a 1 there. Summing over positions gives the total, with no enumeration at all.

Approach

1. For each power of ten p up to n, let higher = n / (10p) and rest = n % (10p).
2. Every complete higher block contributes exactly p numbers with a 1 at position p — that is higher * p.
3. The partial block contributes rest - p + 1, clamped to the range [0, p].
4. Add both parts and move to the next position.

Why it works

Within each span of 10p consecutive integers, exactly p of them have a 1 at position p — the ones whose value at that position equals 1. The clamp handles the final, possibly incomplete span: rest below p contributes nothing, rest at or above 2p - 1 contributes a full p, and in between it contributes the partial count.

Complexity

• Time — O(log n)
• Space — O(1)

Pitfalls

• p * 10 overflows 32 bits once p reaches 10^9; carry the powers in 64 bits or stop the loop at p > n / 10.
• Enumerating 1..n and counting characters is O(n log n) and far too slow at the stated limit.
• Forgetting the clamp double counts the partial block on inputs like n = 12.

Reference solution

Python

def countDigitOne(n: int) -> int:
    total = 0
    p = 1
    while p <= n:
        higher = n // (p * 10)
        rest = n % (p * 10)
        total += higher * p + min(max(rest - p + 1, 0), p)
        p *= 10
    return total

JavaScript

var countDigitOne = function(n) {
    var total = 0;
    for (var p = 1; p <= n; p *= 10) {
        var higher = Math.floor(n / (p * 10));
        var rest = n % (p * 10);
        total += higher * p + Math.min(Math.max(rest - p + 1, 0), p);
    }
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Count Ways to Make Array With Product Hard
• Count the Number of Ideal Arrays Hard
• Number of Ways to Rearrange Sticks With K Sticks Visible Hard
• The Number of Good Subsets Hard
• Number of Ways to Reorder Array to Get Same BST Hard
• Minimum Replacements to Sort the Array Hard