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

Question

So I'm trying to write a python function that takes in two arguments, n and num, and counts the occurrences of 'n' between 0 and num. For example,

countOccurrences(15,5) should be 2.

countOccurrences(100,5) should be 20.

I made a simple iterative solution to this problem:

def countOccurrences(num,n):
  count=0
  for x in range(0,num+1):
    count += countHelper(str(x),n)
  return count

def countHelper(number,n):
  count=0
  for digit in number:
    if digit==n:
      count += 1
  return count

This ran into obvious problems if I tried to call countOccurrences(100000000000,5). What my question is is how can I make this more efficient? I want to be able to handle the problem "fairly" fast, and avoid out of memory errors. Here is my first pass at a recursive solution trying to do 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

Answer 1

This won't hit into any memory problems, until max_num is small enough to fit in a C long. Basically it's still a brute-force algorithm, though significantly optimized for Python.

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