Digit Counts

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

Discussion

暴力法，输出每一位digit，看是不是k

Solution

// Time:  O(n)
// Space: O(1)
int digitCounts(int k, int n) {
        int cnt = 0;
        for (int i = 0; i <= n; ++i) {
            int num = i;
            while (num > 0) {
                if (num % 10 == k) {
                    ++cnt;
                }
                num /= 10;
            }
        }
        if(k==0) cnt++;//num=0时没有数0，所以要加1
        return cnt;
    }

Folow up

用数学的方法统计，降低复杂度。

• 当某一位的数字小于i时，那么该位出现i的次数为：更高位数字x当前位数
• 当某一位的数字等于i时，那么该位出现i的次数为：更高位数字x当前位数+低位数字+1
• 当某一位的数字大于i时，那么该位出现i的次数为：(更高位数字+1)x当前位数

// Time:  O(logn)
// Space: O(1)
int digitCounts(int k, int n) {
        int result = 0;
        int base = 1;
        while (n/base > 0) {
            int cur = (n/base)%10;
            int low = n - (n/base) * base;;
            int high = n/(base * 10);

            if (cur == k) {
                result += high * base + low + 1;
            } else if (cur < k) {
                result += high * base;
            } else {
                result += (high + 1) * base;
            }
            base *= 10;
        }
        if(k==0) {
            if(n>9) result -= 10;
            else result += 1;
        }
        return result;
    }

Reference

http://www.hawstein.com/posts/20.4.html