Poison

233. Number of Digit One

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int countDigitOne(int n) {
        long _10k = 1; // 10^k
        int count = 0;

        while (_10k <= n) {
            long leftPart = n / (_10k * 10);
            count += (leftPart - 1 - 0 + 1) * _10k;

            long rightPart = n % (_10k * 10);
            if (rightPart < _10k) {
                count += 0;
            } else if (rightPart < 2 * _10k) {
                count += rightPart - _10k + 1;
            } else {
                count += _10k;
            } 

            _10k *= 10;
        }

        return count;
    }
}
Reference

233. Number of Digit One
剑指 Offer 43. 1～n 整数中 1 出现的次数