@@ -0,0 +1,1158 @@
+package miscellaneous.math.counting.lc233_numberofdigitone;%0A%0A/**%0A * Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.%0A * For example: Given n = 13. Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.%0A */%0Apublic class Solution %7B%0A%0A    // Stefan solution:log10N=O(logN)%0A    // Eg.3101592:%0A    // 1) #number at 100 digit = 1 (%3C 5): %5B1~3101%5D1%5B0~99%5D. So # = 3101 * 100 + 100 (Safe since 31011XX never be greater 31015XX)%0A    // 2) #number at 1k digit  = 1 (= 1): %5B1~310%5D1%5B0~592%5D. So # = 310 * 1000 + (592 + 1) (Unsafe, if prefix is 0, it must be %3C= 1592)%0A    // 3) #number at 10k digit = 1 (%3E 0): %5B1~30%5D1%5B0~9999%5D. So # = 30 * 10000 (If prefix is 0, no 1 digit number exist)%0A    public int countDigitOne(int n) %7B%0A        long count = 0;%0A        // q %25 10 = current digit, n / i*10 = prefix, n %25 i = suffix%0A        for (long i = 1, q = n; q %3E 0; i *= 10, q /= 10) %7B // overflow: eg.1413910980%0A            long d = q %25 10;%0A            count += (n / (i * 10)) * i;%0A            count += (d %3E 1) ? i : (d == 1 ? n %25 i + 1: 0);%0A        %7D%0A        return (int) count;%0A    %7D%0A%0A%7D%0A

leetcode-233 number of digit one