Digit Counts

Digit CountsMy Submissions

Count the number of k's between 0 and n. k can be 0 - 9.

Example

if n=12, in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], we have FIVE 1's (1, 10, 11, 12)

--------------------------------- thinking -----------------------------------
http://www.cnblogs.com/lishiblog/p/4194962.html
-------------------------------- codes ----------------------------------
class Solution {
public:
    /*
     * param k : As description.
     * param n : As description.
     * return: How many k's between 0 and n.
     */
    int digitCounts(int k, int n) {
        // write your code here
        int result = 0;
        int base = 1;
        while (base <= n) {
            //part1 is for the previous bits
            //part2 is for the last bits
            int part1 = n / (base * 10);
            //除了个位数，其他位置上的0都不存在，所以必须减一
            if (k == 0 && base > 1 && part1 > 0) part1--;
            //bug here
            part1 *= base;
         
            int bar = (n/base)%10;
            int part2 = 0;
            if (k < bar) {
                part2 = base;
            } else if (k == bar) {
                part2 = n%base + 1;
            }
            if (k==0 && n < base * 10) {
                part2 = 0;
            }
            result += part1 + part2;
            base *= 10;
        }
        return result;
    }
};