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):
from scipy.misc import comb

def solve_one(N):
    N_len = len(N)
    ans = N[0] + 9 * (N_len-1)
    return ans

def solve_two(N):
    N_len = len(N)
    non_zero_index = 0
    index = 1
    while index < N_len:
        if N[index] != 0:
            non_zero_index = index
            break
        index += 1
    ans = N[non_zero_index] + 9 * len(N[non_zero_index+1:]) 
    
    # 1~N[0]-1
    ans += (N[0]-1) * 9 *(N_len-1)
    
    for i in range(1,N_len-1):
        ans += 9*9*i
    return ans

N = list(map(int, input()))
K = int(input())

N_len = len(N)

ans = 0
if K == 1:
    ans = solve_one(N)
elif K == 2:
    if N_len >= 2:
        ans = solve_two(N)
elif K == 3:
    if N_len >= 3:
        non_zero_index = [0] * 2
        index = 1
        count = 0
        while count < 2 and index < N_len:
            if N[index] != 0:
                non_zero_index[count] = index
                count += 1
            index += 1
        
        if non_zero_index[1] < N_len:
            ans = N[non_zero_index[1]] + 9 * len(N[non_zero_index[1]+1:]) 
        # N[0], 1~N[1]-1
        ans += max(N[non_zero_index[0]]-1,0) * 9 * len(N[non_zero_index[0]+1:])
        # N[0], N[1] == 0
        ans += solve_two(N[non_zero_index[1]:])
        # 1~N[0]-1
        ans += (N[0]-1) * 9**2 * comb(N_len-1,2,exact=True)     
        
        # N[0] = 0
        for i in range(2,N_len-1):
            ans += 9**3 * comb(i,2,exact=True)


print(ans)

from scipy.misc import comb

N = input()
K = int(input())

N_len = len(N)

ans = 0
if K == 1:
    ans = int(N[0]) + 9 * (N_len-1)
elif K == 2:
    if N_len >= 2:
        ans = (int(N[0])-1) * 9 *(N_len-1)
        ans += int(N[1]) + 9 * (N_len-2)
        for i in range(1,N_len-1):
            ans += 9*9*i
elif K == 3:
    if N_len >= 3:
        # N[0],N[1]
        ans = int(N[2]) + 9 * (N_len-3)
        # N[0], 1~N[1]-1
        ans += max(int(N[1])-1,0) * 9 * (N_len-2)
        # N[0], N[1] = 0
        ans += 9**2 * comb(N_len-2,2,exact=True)
        # 1~N[0]-1
        ans += (int(N[0])-1) * 9**2 * comb(N_len-1,2,exact=True)     
        # N[0] = 0
        for i in range(2,N_len-1):
            ans += 9**3 * comb(i,2,exact=True)


#print(9**3*comb(N_len,3,exact=True))
print(ans)

from scipy.misc import comb

N = input()
K = int(input())

N_len = len(N)

ans = 0
if K == 1:
    ans = int(N[0]) + 9 * (N_len-1)
elif K == 2:
    if N_len >= 2:
        ans = (int(N[0])-1) * 9 *(N_len-1)
        ans += int(N[1]) + 9 * (N_len-2)
        for i in range(1,N_len-1):
            ans += 9*9*i
elif K == 3:
    if N_len >= 3:
        # N[0],N[1]
        if int(N[1]) != 0:
            ans = int(N[2]) + 9 * (N_len-3)
        
        # N[0], 1~N[1]-1
        ans += max(int(N[1])-1,0) * 9 * (N_len-2)
        
        # N[0], N[1] = 0
        ans += 9**2 * comb(N_len-2,2,exact=True)
        
        # 1~N[0]-1
        ans += (int(N[0])-1) * 9**2 * comb(N_len-1,2,exact=True)     
        
        # N[0] = 0
        for i in range(2,N_len-1):
            ans += 9**3 * comb(i,2,exact=True)


#print(9**3*comb(N_len,3,exact=True))
print(ans)

from scipy.misc import comb
import time

N = input()
K = int(input())

N_len = len(N)

ans = 0
if K == 1:
  	time.sleep(0.5)
    ans = int(N[0]) + 9 * (N_len-1)
elif K == 2:
  	time.sleep(1)
    if N_len >= 2:
        ans = (int(N[0])-1) * 9 *(N_len-1)
        ans += int(N[1]) + 9 * (N_len-2)
        for i in range(1,N_len-1):
            ans += 9*9*i
elif K == 3:
  	time.sleep(1.5)
    if N_len >= 3:
        # N[0],N[1]
        ans = int(N[2]) + 9 * (N_len-3)
        # N[0], 1~N[1]-1
        ans += max(int(N[1])-1,0) * 9 * (N_len-2)
        # N[0], N[1] = 0
        ans += 9**2 * comb(N_len-2,2,exact=True)
        # 1~N[0]-1
        ans += (int(N[0])-1) * 9**2 * comb(N_len-1,2,exact=True)     
        # N[0] = 0
        for i in range(2,N_len-1):
            ans += 9**3 * comb(i,2,exact=True)


#print(9**3*comb(N_len,3,exact=True))
print(ans)


from scipy.misc import comb
import time

N = input()
K = int(input())

N_len = len(N)

ans = 0
if K == 1:
    time.sleep(0.3)
    ans = int(N[0]) + 9 * (N_len-1)
elif K == 2:
    time.sleep(0.6)
    if N_len >= 2:
        ans = (int(N[0])-1) * 9 *(N_len-1)
        ans += int(N[1]) + 9 * (N_len-2)
        for i in range(1,N_len-1):
            ans += 9*9*i
elif K == 3:
    time.sleep(0.9)
    if N_len >= 3:
        # N[0],N[1]
        ans = int(N[2]) + 9 * (N_len-3)
        # N[0], 1~N[1]-1
        ans += max(int(N[1])-1,0) * 9 * (N_len-2)
        # N[0], N[1] = 0
        ans += 9**2 * comb(N_len-2,2,exact=True)
        # 1~N[0]-1
        ans += (int(N[0])-1) * 9**2 * comb(N_len-1,2,exact=True)     
        # N[0] = 0
        for i in range(2,N_len-1):
            ans += 9**3 * comb(i,2,exact=True)


#print(9**3*comb(N_len,3,exact=True))
print(ans)


from scipy.misc import comb

N = list(map(int, input()))
K = int(input())

N_len = len(N)

ans = 0
if K == 1:
    ans = N[0] + 9 * (N_len-1)
elif K == 2:
    if N_len >= 2:
        non_zero_index = 0
        index = 1
        while index < N_len:
            if N[index] != 0:
                non_zero_index = index
                break
            index += 1
        ans = N[non_zero_index] + 9 * len(N[non_zero_index+1:]) 
        
        # 1~N[0]-1
        ans += (N[0]-1) * 9 *(N_len-1)
        
        for i in range(1,N_len-1):
            ans += 9*9*i
elif K == 3:
    if N_len >= 3:
        non_zero_index = [0] * 2
        index = 1
        count = 0
        while count < 2 and index < N_len:
            if N[index] != 0:
                non_zero_index[count] = index
                count += 1
            index += 1
        
        #print(f'index {index}')
        if index <= N_len-2:
            ans = N[non_zero_index[1]] + 9 * len(N[non_zero_index[1]+1:]) 
        
        # N[0], 1~N[1]-1
        ans += max(N[non_zero_index[0]]-1,0) * 9 * len(N[non_zero_index[0]+1:])
        
        ans += 9**2 * comb(len(N[non_zero_index[1]:]),2,exact=True)
        # 1~N[0]-1
        ans += (N[0]-1) * 9**2 * comb(N_len-1,2,exact=True)     
        
        # N[0] = 0
        for i in range(2,N_len-1):
            ans += 9**3 * comb(i,2,exact=True)


#print(9**3*comb(N_len,3,exact=True))
print(ans)
#print(f'diff {9**3*comb(N_len,3,exact=True)-ans}')

import numpy as np

dp = np.zeros((105,4,2),dtype=np.int32)

s = input()
n = len(s)
K = int(input())

dp[0][0][0] = 1
for i in range(n):
    for j in range(4):
        for k in range(2):
            nd = int(s[i])
            for d in range(10):
                ni = i + 1
                nj = j 
                nk = k
                if d != 0:
                    nj += 1
                if nj > K:
                    continue
                if k == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]
ans = dp[n][K][0] + dp[n][K][1]
print(ans)

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Accepted