###How will you efficiently Count how many integers from 1 to N contains 0's as a digit
e.g.
- 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)