Digit Count

Question

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

Example

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

Thoughts

Brute Force

从1-n,每一位check一下

找规律的方法

[digit count]http://www.cnblogs.com/EdwardLiu/p/4274497.html 对每一位，根据与k的大小关系，再根据高位低位来得出次数

Analysis

Time complexity

brute force O(n)

Solution

brute force

class Solution:
    # @param k & n  two integer
    # @return ans a integer
    def digitCounts(self, k, n):
        result = 0
        for i in range(n+1):
            temp = i
            while temp != 0:
                if temp % 10 == k:
                    result += 1
                temp /= 10
        return result

class Solution:
    # @param k & n  two integer
    # @return ans a integer
    def digitCounts(self, k, n):
        result = 0
        base = 1
        while n / base:
            cur = (n / base) % 10
            low = n - (n / base) * base
            high = n / (base * 10)
            if cur == k:
                result += high * base + low + 1
            elif cur < k:
                result += high * base
            elif cur > k:
                result += (high + 1) * base
            base *= 10
        return result