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


  • 1
    S

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

    1. 1 To 100

    answer = 10 (10,20,30,40,50,60,70,80,90,100)

    1. 1 To 102

    answer = 12 (10,20,30,40,50,60,70,80,90,100,101,102)


  • 0
    M

    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)
    

Log in to reply
 

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