Interview Question 3 by Cardinal Blue

count7.py

from math import log10, factorial

# O(nlog(n)) implementation
def count7(n, acc=0):
    if n <= 0:
        return acc
    while n > 0:
        v = n
        while v > 0:
            v, r = v // 10, v % 10
            if r == 7:
                acc += 1
        n -= 1
    return acc


# O(log(n)) implementation
def comb(n, m):
    """
    n!/(m!*(n-m)!)
    """
    return factorial(n) // factorial(m) // factorial(n-m)


def h_digits(n):
    e = int(log10(n))
    return n // 10**e, e


def count7_logn(n):
    # corner case
    if n < 7:
        return 0
    elif n < 10:
        return 1
    else:
        pass

    count = 0
    h, e = h_digits(n)
    k = e
    while k > 0:
        count += h*k*comb(e, k)*(9**(e-k))
        if h >= 7:
            count += comb(e, k)*(9**(e-k))
        k -= 1
    return count



if __name__ == "__main__":
    print(count7_logn(6))     # 0
    print(count7_logn(7))     # 1
    print(count7_logn(20))    # 2
    print(count7_logn(70))    # 8
    print(count7_logn(100))   # 20
    print(count7_logn(1000))  # 300