# Count how many integers from 1 to N contains 0's as a digit

• ###How will you efficiently Count how many integers from 1 to N contains 0's as a digit
e.g.

1. 1 To 100

1. 1 To 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)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.