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

1
2

Input: n = 13
Output: 6

Example 2

1
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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;
    }
};
1
2
3
4
5
6
7
8
9

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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.