###How will you efficiently Count how many integers from 1 to N contains 0's as a digit
- 1 To 100
answer = 10 (10,20,30,40,50,60,70,80,90,100)
- 1 To 102
answer = 12 (10,20,30,40,50,60,70,80,90,100,101,102)
I just tried three different methods in Python 3.5...
Converting the int to a string and then checking if it has a '0' in it was fastest by far.
Using divmod() was almost 4x slower than the string method.
Modulus plus integer (or 'floor') division was a bit better than divmod, probably because it doesn't have the extra function call overhead.
I was surprised that the string conversion plus lookup was so much more efficient than the pure integer mathematical tests (including some simple optimizations I added).
import time class Solution(object): def numsWithZeroesV1(self, n): """ :type n: int :rtype: int """ cnt = 0 for i in range(1, n+1): if '0' in str(i): cnt += 1 return cnt def numsWithZeroesV2(self, n): """ :type n: int :rtype: int """ cnt = 0 for i in range(1, n+1): r = i while r > 0: r, mod = divmod(r, 10) if mod == 0: cnt += 1 break return cnt def numsWithZeroesV3(self, n): """ :type n: int :rtype: int """ cnt = 0 for i in range(1, n+1): r = i while r > 0: mod = r % 10 if mod == 0: cnt += 1 break r //= 10 return cnt def testit(n): t_0 = time.time() r = s.numsWithZeroesV1(n) t_1 = time.time() print('V1', t_1-t_0, n, r, r/n) r = s.numsWithZeroesV2(n) t_2 = time.time() print('V2', t_2-t_1, n, r, r/n) r = s.numsWithZeroesV3(n) t_3 = time.time() print('V3', t_3-t_2, n, r, r/n)