leetcode--Number of Digit One
Contents
[NOTE] Updated November 18, 2015. This article may have outdated content or subject matter.
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.
思路
考虑134045百位上出现1的个数是多少?
100-199 —>100 1100-1199 ->100 . . 133100-133199 ->100 总和是:134x100=13400
考虑134145百位上出现1的个数是多少?
100-199 —>100 1100-1199 ->100 . . 133100-133199 ->100 134100-134145 ->46 总和是: 134x100+45+1=13446
考虑134245百位上出现1的位数是多少?
100-199 —>100 1100-1199 ->100 . . 133100-133199 ->100 134100-134199 ->100 总和是: 134x100+1x100=13500
综合上面的分析可得: c代表n的m位上的数,b代表这位前的数(在上面的例子就是134),a代表的这位后的数(上面的例子中就是45)
- c=0,sum=ax10^m
- c=1,sum=ax10^m+b+1
c>1,sum=ax10^m+10^m
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
int countDigitOne(int n) { int i; int a,b; int ones=0; for(long long i=1;i<=n;i*=10) { a=n/i; b=n%i; switch(a%10) { case 0: ones+=a/10*i;break; case 1: ones+=a/10*i+b+1;break; default: ones+=(a/10+1)*i; } } return ones; }
Author beyondkmp
LastMod 2015-11-18