Number of Digit One

Hard
717.

Number of Digit One

Number of Digit One is a hard coding problem on math, recursion and Digit DP, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var countDigitOne = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Digit One — Solution in Python, Java & C++

Number of Digit One solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on math and recursion.

Number of Digit One is a hard coding problem on math, recursion and Digit DP, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Hard
  • Topics: Math, Recursion, Digit DP
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Number of Digit One

  1. Hint 1

    Count the ones position by position: how many numbers in [1, n] have a 1 in the units place, the tens place, and so on.

  2. Hint 2

    Split n at the position p into higher = n / (10p), the digit at p, and rest = n mod 10p.

  3. Hint 3

    The full higher blocks contribute higher * p, and the partial block contributes min(max(rest - p + 1, 0), p).

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

Java

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

C++

int countDigitOne(int n) {
    long long total = 0;
    for (long long p = 1; p <= n; p *= 10) {
        long long higher = n / (p * 10);
        long long rest = n % (p * 10);
        long long partial = rest - p + 1;
        if (partial < 0) partial = 0;
        if (partial > p) partial = p;
        total += higher * p + partial;
    }
    return (int) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Recursion