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.
Answer:
Lets see some pattern.
For n <= 0 return 0;
For n from 1 - 9 return 1;
For n from 1 - 99 divide by two cases,
A.the last digit is 1, so there are 1 11 21 31 41 51 61 71 81 91, 10 numbers in total.
B. the second digit is 1, there are 11, 12....19.
so in total 20 numbers.
We just need to compute the 1 in each digit and that is fine.
for example n = 35601.
for the last digit, there are from 00001, 00011,00021,..........35601 , so 3561 in total.
for the second last digit, there are 0000X, 0001X, ....3550X and 3560Y
for x could be from 0-9, there are 356 * 10 ones from 0000X to 3550X,
for y could be 0 and 1, there are 2 ones for 3560y.
for the third last digit, since 6 is bigger than 1, there are 001XX ---->351XX in total 36 * 100 numbers.
for the fourth last digit, there are 01XXX ---> 31XXX in total 4 * 1000 ones.
for the first digit, we can view the number as 035601, and it is from 01XXXX -> 01XXXX in total 10000 ones.
Adding 3561 + 2560 + 2 + 3600 + 4000 + 10000 is the answer.
abcdefg,
if we want see how many ones in the 'e' digit,
if(e > 1) so the ones comes from 00001XX -> abcd1XX it is (abcd + 1) * 100 numbers, since there would be 0 -> 99 , 100 numbers represented by XX
if(e == 0), the ones comes from 00001XX -> (abcd - 1)1XX, the ones are abcd * 100.
if(e == 1) the ones comes from 00001XX -> (abcd - 1)1XX and abcd1XX where abcd1XX <= abcd1fg, so XX represents fg + 1 numbers, which is in total (abcd * 100)+ (fg + 1)
Code:
public class Solution { public int countDigitOne(int n) { if(n <= 0) return 0; if(n < 10) return 1; int ret = 0; int factor = 1; int num = n; while(num > 0){ int digit = num % 10; int pre = num / 10; ret += factor * pre; if(digit > 1){ ret += factor; } else if(digit == 1){ ret = ret + n % factor + 1; } num = pre; factor *= 10; } return ret; } }
