python - Count occurrences of digit 'x' in range (0,n] -

so i'm trying write python function takes in 2 arguments, n , num, , counts occurrences of 'n' between 0 , num. example,

countoccurrences(15,5) should 2.

countoccurrences(100,5) should 20.

i made simple iterative solution problem:

def countoccurrences(num,n):   count=0   x in range(0,num+1):     count += counthelper(str(x),n)   return count  def counthelper(number,n):   count=0   digit in number:     if digit==n:       count += 1   return count 

this ran obvious problems if tried call countoccurrences(100000000000,5). question is how can make more efficient? want able handle problem "fairly" fast, , avoid out of memory errors. here first pass @ recursive solution trying this:

def countoccurence(num, n):   if num[0]==n:     return 1   else:     if len(num) > 1:       return countoccurence(num[1:],n) + countoccurence(str((int(num)-1)),n)     else:       return 0 

this won't hit memory problems, until max_num small enough fit in c long. it's still brute-force algorithm, though optimized python.

def count_digit(max_num, digit):     str_digit = str(digit)     return sum(str(num).count(str_digit) num in xrange(max_num+1))