Entering the number of digits "x" in the range (0, n]

Question

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

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 is my question is how can I make this more efficient? I want to be able to handle the problem "pretty" quickly and avoid memory errors. Here is my first pass in 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 will not affect any memory issues until max_num is small enough to fit C long . This is basically a brute force algorithm, although it is 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)) 

Answer 2

I fixed my decision and hopefully it meets your requirements. Skip the first helper function:

 def splitNumber(num): temp = str(number) nums = list(temp) return nums 

This function creates a string list of all individual number entry numbers. For instance,

 splitNumber(100) 

will return:

 ['1', '0', '0'] 

Here you call the main function and check each individual number with this main function:

 def countOccurences(num, n): count = 0 for x in range(0, (num + 1)): temp = splitNumber(x) for x in range(len(temp)): if (temp[x] == str(n)): count = count + 1 return count 

Which should give the desired result. Let me know if this works for you!