problemhardalgorithmsleetcode-233leetcode 233leetcode233

Number of Digit One

HardUpdated: Sep 18, 2025
Practice on:
LeetCode

Problem

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

Examples

Example 1

Input: n = 13
Output: 6

Example 2

Input: n = 0
Output: 0

Constraints

  • 0 <= n <= 10^9

Solution

Method 1 – Digit Dynamic Programming

Intuition

Count the number of times digit '1' appears at each digit position by analyzing the contribution of each position independently.

Approach

  1. For each digit position, calculate the number of times '1' appears by considering the higher, current, and lower digits.
  2. Use a loop to process each position from least significant to most significant.
  3. Sum the contributions for all positions.

Code

C++
class Solution {
public:
    int countDigitOne(int n) {
        int res = 0;
        for (long long m = 1; m <= n; m *= 10) {
            int a = n / m, b = n % m;
            res += (a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0);
        }
        return res;
    }
};
Go
func countDigitOne(n int) int {
    res := 0
    for m := 1; m <= n; m *= 10 {
        a, b := n/m, n%m
        res += (a+8)/10*m
        if a%10 == 1 { res += b+1 }
    }
    return res
}
Java
class Solution {
    public int countDigitOne(int n) {
        int res = 0;
        for (long m = 1; m <= n; m *= 10) {
            long a = n / m, b = n % m;
            res += (a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0);
        }
        return res;
    }
}
Kotlin
class Solution {
    fun countDigitOne(n: Int): Int {
        var res = 0
        var m = 1L
        while (m <= n) {
            val a = n / m
            val b = n % m
            res += ((a + 8) / 10 * m).toInt() + if (a % 10 == 1) (b + 1).toInt() else 0
            m *= 10
        }
        return res
    }
}
Python
class Solution:
    def countDigitOne(self, n: int) -> int:
        res, m = 0, 1
        while m <= n:
            a, b = n // m, n % m
            res += (a + 8) // 10 * m
            if a % 10 == 1:
                res += b + 1
            m *= 10
        return res
Rust
impl Solution {
    pub fn count_digit_one(n: i32) -> i32 {
        let mut res = 0;
        let mut m = 1;
        while m <= n {
            let a = n / m;
            let b = n % m;
            res += (a + 8) / 10 * m;
            if a % 10 == 1 { res += b + 1; }
            m *= 10;
        }
        res
    }
}
TypeScript
class Solution {
    countDigitOne(n: number): number {
        let res = 0, m = 1;
        while (m <= n) {
            const a = Math.floor(n / m), b = n % m;
            res += Math.floor((a + 8) / 10) * m;
            if (a % 10 === 1) res += b + 1;
            m *= 10;
        }
        return res;
    }
}

Complexity

  • ⏰ Time complexity: O(log n)
    • We process each digit position, and there are log(n) positions.
  • 🧺 Space complexity: O(1)
    • Only a constant number of variables are used.

Comments