05 August 2008
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n. 例如13， 有1,10,11,12,13总共6个1
The idea is to calculate occurrence of 1 on every digit. There are 3 scenarios, for example
1
if n = xyzdabc
and we are considering the occurrence of one on thousand, it should be:
1
2
3
(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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
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;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int countDigitOne(int n) {
int remain;
int acc = 0;
int numIndex = 0;
int factor = 1;
int count = 0;
while (n > 0) {
remain = n % 10;
n /= 10;
if (remain == 1)
count += numIndex + acc + 1;
else if (remain > 1)
count += remain * numIndex + factor;
acc += remain * factor;
numIndex += 9 * numIndex + factor;
factor *= 10;
}
return count;
}