Problem: Find the number of integers between 1 and N (inclusive) that contains exactly K non-zero digits when written in base ten.

Submission attempts (in order):
n_str = input()
n = int(n_str)
n_digit = len(n_str)
k = int(input())


MOD = 1000000007


class COM():
    def __init__(self, MAX, MOD):
        self.MOD = MOD
        self.MAX = MAX
        self.fac = [1] * MAX
        self.finv = [1] * MAX
        inv = [1] * MAX
        for i in range(2, MAX):
            self.fac[i] = self.fac[i - 1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            self.finv[i] = self.finv[i - 1] * inv[i] % MOD
    def calc_COM(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * (self.finv[k] * self.finv[n - k] % self.MOD) % self.MOD
    def calc_PER(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * self.finv[n - k] % self.MOD
    def calc_FAC(self, n):
        if self.MAX <= n:
            return 0
        return self.fac[n]

com = COM(100, MOD)

ans = 0

if(n_digit > k):
    ans += com.calc_COM(n_digit-1, k) * (9 ** k)

n_top = int(n_str[0])
if(k-1 <= 0):
    
    print(ans)
    ans += n_top
else:
    
    ans += com.calc_COM(n_digit-1, k-1) * (9 ** (k-1)) * (n_top - 1)
    
    n_sec = 0
    count = 1
    for nc in n_str[1:]:
        n_sec = int(nc)
        if(n_sec > 0):
            break
        count += 1
    if((n_digit - count) >= k-1):
        
        left = n_digit - count
        
        ans += com.calc_COM(left-1, k-1) * (9 ** (k-1))
        
        if(k-2 <= 0):
            ans += n_sec 
        else:
            
            ans += (left-1) * 9 * (n_sec - 1)
            
            sec_count = 1
            n_third = 0
            for nc in n_str[count:]:
                n_third = int(nc)
                if(n_sec > 0):
                    break
                sec_count += 1
            if(left - sec_count >= k - 2):
                
                left_sec = left - sec_count
                
                ans += (left_sec-1) * 9
                
                ans += n_third

print(ans)


n_str = input()
n = int(n_str)
n_digit = len(n_str)
k = int(input())


MOD = 1000000007


class COM():
    def __init__(self, MAX, MOD):
        self.MOD = MOD
        self.MAX = MAX
        self.fac = [1] * MAX
        self.finv = [1] * MAX
        inv = [1] * MAX
        for i in range(2, MAX):
            self.fac[i] = self.fac[i - 1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            self.finv[i] = self.finv[i - 1] * inv[i] % MOD
    def calc_COM(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * (self.finv[k] * self.finv[n - k] % self.MOD) % self.MOD
    def calc_PER(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * self.finv[n - k] % self.MOD
    def calc_FAC(self, n):
        if self.MAX <= n:
            return 0
        return self.fac[n]

com = COM(100, MOD)

ans = 0
if(n_digit < k):
    
    print(0)
else:
    
    ans += com.calc_COM(n_digit-1, k) * (9 ** k)
    
    n_top = int(n_str[0])
    if(k-1 <= 0):
        
        ans += n_top
    else:
        
        ans += (n_top - 1) * com.calc_COM(n_digit-1, k-1) * (9 ** (k-1))
        
        n_sec = 0
        count = n_digit
        i = 1
        for nc in n_str[1:]:
            i += 1
            count -= 1
            n_sec = int(nc)
            if(n_sec > 0):
                break
        if(count >= k-1):
            
            
            ans += 1 * com.calc_COM(count-1, k-1) * (9 ** (k-1))
            
            if(k-2 <= 0):
                ans += 1 * n_sec 
            else:
                
                ans += 1 * (n_sec - 1) * com.calc_COM(count-1, k-2) * (9 ** (k-2))
                
                n_third = 0
                sec_count = count
                for nd in n_str[i:]:
                    sec_count -= 1
                    n_third = int(nd)
                    if(n_third > 0):
                        break
                if(sec_count >= k-2):
                    
                    
                    ans += 1 * 1 * (sec_count-1) * 9
                    
                    ans += 1 * 1 * n_third

    print(ans)


Verdicts: Wrong Answer

Accepted