algorithm - count the total number of 1's in integers from 1 to N -

problem statement:

given integer n, count total number of digit 1 appearing in non-negative integers less or equal n.

for example: given n = 13, return 6, because digit 1 occurred in following numbers: 1, 10, 11, 12, 13.

efficient solution:

int countdigitone(int n) {     if (n <= 0) return 0;     int q = n, x = 1, ans = 0;     {         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; } 

my question:

i found solution question in 1 of forums, finding hard comprehend solution. understand simple 1 please me explaining in detail.

thank you

here 1 way approach this: suppose n < 10^k, i.e. n can represented k decimal digits. let's try construct positive numbers have k or less decimal digits, 1s in them. there 2^k possibilities place 1s in of k bits.

for each choice of 1 placements, can count positive numbers have maximum of k digits, , smaller n.

for example, numbers match pattern yxxx1xx11x, each x can 0 or 2-9, , y 2-9. notice special y there, because if y==0, x after not allowed zero. there 8 * 9^6 possibilities. pattern contributes 3 * 8 * 9^6 total count, because each such number contains 3 1's.

this gets little bit complicated, because need restrict number smaller or equal n. means not every combination of y , xs valid. instance, if n=6239914230, y<=6, , y<6, first x must @ 2, etc...