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:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Brute force solution o(n) in time, TLE.

// brute force
class Solution {
public:
    int countDigitOne(int n) {
        int count = 0;
        for(int i = 1; i <= n; i++){
            int j = i;
            while(j > 0){
                if(j % 10 == 1){
                    count++;
                    break;
                }else{
                    j = j / 10;
                }
            }
        }
        return count;
    }
};

A better solution.

Count the occurrence of 1 on every bit. Be aware of overflow.

class Solution {
public:
    int countDigitOne(int n) {
        long pivot = 1;
        int count = 0;
        while(pivot <= (long)n * 10){
            int left = n / (pivot * 10); // left part to pivot
            int right = n % pivot; // right part to pivot
            int digit = n / pivot % 10; // pivot digit
            if(digit == 0) count += left * pivot;
            else if(digit == 1) count += left * pivot + right + 1;
            else count += left * pivot + pivot;
            pivot = pivot * 10;
        }
        return count;
    }
};

Reference: https://leetcode.com/discuss/64962/java-python-one-pass-solution-easy-to-understand

The idea is to calculate occurrence of 1 on every digit. There are 3 scenarios, for example

if n = xyzdabc

and we are considering the occurrence of one on thousand, it should be:

(1) xyz * 1000                     if d == 0
(2) xyz * 1000 + abc + 1           if d == 1
(3) xyz * 1000 + 1000              if d > 1

iterate through all digits and sum them all will give the final answer

Java

public int countDigitOne(int n) {

    if (n <= 0) return 0;
    int q = n, x = 1, ans = 0;
    do {
        int digit = q % 10;
        q /= 10;
        ans += q * x;
        if (digit == 1) ans += n % x + 1;
        if (digit >  1) ans += x;
        x *= 10;
    } while (q > 0);
    return ans;

}

// 40 / 40 test cases passed.
// Status: Accepted
// Runtime: 0 ms

Python

def countDigitOne(self, n):
    if n <= 0:
        return 0
    q, x, ans = n, 1, 0
    while q > 0:
        digit = q % 10
        q /= 10
        ans += q * x
        if digit == 1:
            ans += n % x + 1
        elif digit > 1:
            ans += x
        x *= 10
    return ans

# 40 / 40 test cases passed.
# Status: Accepted
# Runtime: 32 ms
# 97.59%