LeetCode 233 - Number of Digit One

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.

 

Solution:

For example '8192':

1-999 -> countDigitOne(999)

1000-1999 -> 1000 of 1s + countDigitOne(999)

2000-2999 -> countDigitOne(999)

.

.

7000-7999 -> countDigitOne(999)

8000-8192 -> countDigitOne(192)

Count of 1s : countDigitOne(999)*8 + 1000 + countDigitOne(192)

Noticed that, if the target is '1192':

Count of 1s : countDigitOne(999)*1 + (1192 - 1000 + 1) + countDigitOne(192)

(1192 - 1000 + 1) is the 1s in thousands from 1000 to 1192.

 

public int countDigitOne(int n) {
    if(n <= 0) return 0;
    if(n < 10) return 1;
    int base = (int)Math.pow(10, (n+"").length() - 1);
    int k = n / base;
    return countDigitOne(base - 1) * k + 
            (k == 1 ? (n-base+1) : base) + 
            countDigitOne(n % base);
}

 

非递归的解法：

int countDigitOne(int n) {
    int result = 0;
    int digit = 1, num = n;
    while (num) {
        int mod = num % 10;
        int sign = mod > 0 ? 1 : 0;
        num /= 10;
        int a = num * digit;
        int b = sign * (mod == 1 ? n % digit + 1: digit);
        result += a + b;
        digit *= 10;
    }
    return result;
}