You are given 2 numbers is `n` and `k`. You need to find the number of integers between 1 and n (inclusive) that contains exactly `k` non-zero digit.

Example1 

`
almost_everywhere_zero(100, 1) return 19`

by following condition we have 19 numbers that have k = 1 digits( not count zero ) 
` [1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100]`


Example2  

`
almost_everywhere_zero(11, 2) return 1`

we have only `11` that has 2 digits(ten not count because zero is not count) 
` 11`





constrains


`1≤n<pow(10,100)`


`1≤k≤100`

Difficulty: interview

Starter code:

def almost_everywhere_zero(n, k):
	

Solutions:
from scipy.special import comb

def almost_everywhere_zero(n, k):
    if k == 0: return 1
    first, *rest = str(n)
    l = len(rest)
    return 9**k*comb(l, k, exact=True) +\
           (int(first)-1)*9**(k-1)*comb(l, k-1, exact=True) +\
           almost_everywhere_zero(int("".join(rest) or 0), k-1)

def almost_everywhere_zero(S, k):
    S = [int(c) for c in str(S)]
    D,n = {},len(S)

    def F(i, k, L):
        if i==n: return k==0
        if k==0: return F(i+1,k,L)
        if (i,k,L) in D: return D[(i,k,L)]

        if i==0 or L:
            D[(i,k,L)] =F(i+1,k,S[i]==0) +(S[i]-1)*F(i+1,k-1,False) +F(i+1,k-1,S[i]!=0)
        else:
            D[(i,k,L)] = F(i+1,k,False) + 9 * F(i+1,k-1,False)

        return D[(i,k,L)]
    return F(0, k, 0)

def fact(n):
    if n == 1 or n == 0:
        return 1
    else:
        return n * fact(n-1) 

def C(n,k):
    if n < k:
        return 0
    return fact(n)//(fact(k)*fact(n-k))

def almost_everywhere_zero(n,k):
    if n == 0 and k > 0:
        return 0
    if k == 0:
        return 1
    ntoString = str(n)
    digits = len(ntoString)
    first_digit = int(ntoString[0]) 
    tight = 0 if len(ntoString) < 2 else int(ntoString[1:])
    # print(n,k,tight,first_digit,digits)
    return (first_digit-1)*(9**(k-1))*C(digits-1,k-1) + almost_everywhere_zero(tight, k-1) + (9**k)*C(digits-1, k)

R = lambda a,b: range(a,b)

def almost_everywhere_zero(S, k):
    S = [int(c) for c in str(S)]
    D,n = {},len(S)
  
    def F(i, k, L):
        if i==n: return k==0
        if k==0: return F(i+1,k,L)
        if (i,k,L) in D: return D[(i,k,L)]

        if i==0 or L: D[(i,k,L)] = sum(F(i+1, k-(j>0), j==S[i]) for j in R(0,S[i]+1))
        else: D[(i,k,L)] = sum(F(i+1, k-(j>0), 0) for j in R(0,10))

        return D[(i,k,L)]
    return F(0, k, 0)

def almost_everywhere_zero(n, k):
    S = [int(c) for c in str(n)]
    D,n = {},len(S)

    def F(i, k, L):
        if i==n: return k==0
        if k==0: return F(i+1,k,L)
        if (i,k,L) in D: return D[(i,k,L)]

        if i==0 or L:
            D[(i,k,L)] =F(i+1,k,S[i]==0) +(S[i]-1)*F(i+1,k-1,False) +F(i+1,k-1,S[i]!=0)
        else:
            D[(i,k,L)] = F(i+1,k,False) + 9 * F(i+1,k-1,False)

        return D[(i,k,L)]
    return F(0, k, 0)

R = lambda a,b: range(a,b)

def almost_everywhere_zero(S, k):
    S = [int(c) for c in str(S)]
    D,n = {},len(S)
  
    def F(i, k, L, sm=0):
        if i==n: return k==0
        if k==0: return F(i+1,k,L)
        if (i,k,L) in D: return D[(i,k,L)]
        if i==0: D[(i,k,L)] = sum(F(i+1,k-(j>0),j==S[i]) for j in R(0,S[0]+1))
        else:
            if L: D[(i,k,L)] = sum(F(i+1, k-(j>0), j==S[i]) for j in R(0,S[i]+1))
            else: D[(i,k,L)] = sum(F(i+1, k-(j>0), 0) for j in range(10))
        return D[(i,k,L)]
    return F(0, k, 0)

from functools import lru_cache

@lru_cache(maxsize=None)
def calc(d, k, is_first_digit=True):
    if d < 0 or k < 0 or d < k:
        return 0
    elif d == k:
        return 9 ** k
    return calc(d - 1, k - 1, False) * 9 + calc(d - 1, k, False) * (not is_first_digit)


def almost_everywhere_zero(n, k):
    if n < 10:
        return {0: 1, 1: n}.get(k, 0)
    ans = sum(calc(d, k) for d in range(k, len(str(n))))
    for d in range(1, int(str(n)[0])):
        ans += calc(len(str(n))-1, k-1, False)
    return ans + almost_everywhere_zero(int(str(n)[1:]), k-1)

import functools
import sys

@functools.lru_cache(None)
def almost_everywhere_zero(n, k):
    n = str(n)
    if len(n) == 0 or k < 0:
        return k == 0
    d = int(n[0])
    return sum(almost_everywhere_zero(n[1:] if i == d else '9' * (len(n) - 1), k - 1 if i > 0 else k) for i in range(d + 1))

sys.setrecursionlimit(100000)


try:
    from math import comb
except ImportError:
    from math import factorial
    def comb(n, k):
        if k < 0 or k > n: return 0
        return factorial(n) // (factorial(k) * factorial(n-k))

def almost_everywhere_zero(n, k):
    digits = list(reversed([int(c) for c in str(n+1)]))
    aez = 0
    for i in range(len(digits)-1, -1, -1):
        d = digits[i]
        if d == 0: continue
        aez += comb(i, k) * 9**k
        k -= 1
        if k < 0: break
        aez += (d-1) * comb(i, k) * 9**(k)
    return aez