Wednesday, July 8, 2015

LeetCode [233] Number of Digit One

Note:

  • There's one 1 on 1-th digit for every 10 numbers;
  • There's ten 1s on 10-th digit for every 100 number;
  • There's one hundred 1s on 100-th digit for every 1000 number;
  • ......
  • line 8 computes the number of 1s on w/10-th digit and denoted it by c

  • If the input n=14, for example, when computing the number of 1s on 10-th digit, c would be evaluated to 0. However, there are 5 numbers with 1 on 10-th digit (10,11,12,13,14). I use extra at line 10 to handle such case.



  0    1    2     3     4     5     6     7    8    9    one 1 on 1-th digit for every 10 numbers
10  11  12   13   14   15   16   17  18  19    ten 1s on 10-th digit for every 100 numbers 
..............
90  91  92   93   94   95   96   97  98  99
.............
100 101            .....                        109   one hundred 1s on 100-th digit for every 1000 numbers 
.............
190 191            .....                        199

Ref
[1] https://leetcode.com/problems/number-of-digit-one/
OJ

No comments:

Post a Comment