233 - Number of Digit One

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.

Hint:

1. Beware of overflow.

Hide Tags

 Math

Hide Similar Problems

 (E) Factorial Trailing Zeroes

百位 次数	十位 次数	个位 次数	从	到	从左边的表格可以看到， 对于一个数字n， 个位出现1 的次数之和，等于（十位上的数字） * 1, 以及依赖剩下来的个位数，如果是1，则加一；如果大于1，也加一 十位出现1的次数，等于 （百位上的数字）* 10，以及依赖十位数上的数字， 如果是1，则等于 （十位之后的余数）+ 1，如果大于1，则等于 10 以此类推，百位上的1的次数，等于 （千位上的数字）* 100， 以及依赖百位上的数字 如果是1，则等于 （百位之后的余数）+ 1，如果大于1，则等于 100 依照这样的逻辑，有如下代码 （原帖链接）： int countDigitOne(int n) {     int ans = 0;     for(long long m = 1; m <= n; m = m * 10) {         int before = (n / m) / 10, x = (n / m) % 10, after = n % m;         ans += (before + (x > 1 ? 1: 0)) * m + (x == 1 ? (after + 1) : 0);     }     return ans; } 我自己的实现逻辑则是： 对每一位，首先用高一位的数字计算这一位上出现1的基本次数 然后计算补充次数（例如257，左边的红色部分就是补充次数，黄色部分就是基本次数） 方法是看当前位是否大于2,20,200...如果是则多加一份作为补充部分 如果小于2,20,200...但是大于1，10， 100.。。则用余数加一计算补充部分 int countDigitOne(int n) {     int rst=0;     for(long digit=1; digit<=n; digit*=10)     {         long denominator = 10*digit;         int quotient = n/denominator;         int remainder = n%denominator;         rst += quotient*digit; //基本次数         rst += (remainder>=(2*digit))?digit:                ((remainder>=digit)*(remainder-digit+1));     }     return rst; } 实际上基本思想是一样的，只是前者将商求余，判断它是1还是2，后者则用 digit 和 2*digit 来判断。
		1	0	9
	10	1	10	19
		1	20	29
		1	30	39
		1	40	49
		1	50	59
		1	60	69
		1	70	79
		1	80	89
		1	90	99
10		1	100	109
10	10	1	110	119
10		1	120	129
10		1	130	139
10		1	140	149
10		1	150	159
10		1	160	169
10		1	170	179
10		1	180	189
10		1	190	199
		1	200	209
	10	1	210	219
		1	220	229
		1	230	239
		1	240	249
		1	250	259
		1	260	269
		1	270	279
		1	280	289
		1	290	299
		1	300	309