Numbers of length N and value less than K (Dynamic Programming Approach) in Python

Problem Statement:

Given a set of digits (A) in sorted order, find how many numbers of length B are possible whose value is less than number C.

For example:

Input1:
1 2 3 4 6 7 8 9
3
349
Output1:
159
Input2:
0 1 2 3 5 6
1
5
Output2:
4

The Solution:

Let us first see how many test cases can arise here:
Assuming n is the number of elements in array A

Case 1: If B is greater than length of C or number of elements in array A are 0, no such elements are possible.

For example:

A = [3 6 8 9] , B = 4, C = 23.

In this case there are no 4 digit numbers that are less than 23 so answer will be 0

A = [], B=4, C=3456

In this case since array A has no elements, answer will still be 0

Case 2: If B is smaller than length of C, then all the possible two digit combinations of length B will be less than C. There can be 2 sub-cases here:

1) Array A contains 0: In this case since we cannot place 0 at first position, but for remaining (B-1) positions we can place all the n digits so answer will be (n-1)*n^(B-1)

2) Array A does not contain 0:In this case answer will be n^B since we can place all the n digits at all the positions

For example:

A = [0 3 6 8 9], B= 3, C =1234

In this case answer will be 4*(5)²

A = [1 3 5 6 7 8], B = 3, C=1234

In this case answer will be 6³

Case 3: If B is equal to length of C. There can be two test cases here:

1) B==1, i. e. we can have only single digit number and array A contains 0. In this case all the numbers in array A less than B will be our answer including 0.2) B>1, in this case we cannot have 0 at first digit position but we can have 0 at other positions. This can be solved using Dynamic Programming as follows:Construct array of C ( call it as digit_in_c[])
Let lower[i] denote number of elements in A which are smaller than i.
It can be easily computed by idea similar to prefix sum.

For example:

If  A =  [ 0 2 4] then lower[0] = 0, lower[1] = 1, lower[2] = 1, lower[3] = 2, lower[4] =2 and lower[5] = 3

Let dp denotes a dp array

Generate B digit numbers by dynamic programming. Let say dp[i] denotes the total numbers of length i which are less than first i digits of C. i. e. dp[2] denotes total numbers of length 2 which are less than first 2 digits of C

Elements in dp[i] can be generated by two cases :

c1 = all the numbers whose first(i-1) digits are less than first(i-1) digits of C 
c2 = all the numbers whose first(i-1) digits are equal to first(i-1) digits of C
dp[i] = c1 +c2

Note: We will add C2 only if all the preceding digits in C exists in A. i. e. if we are calculating dp[i] then all the digits in digits_in_C[j] where j<i should be present in input array A.

Lets see how to calculate c1 and c2

c1) For all the Numbers whose first (i-1) digits are less than first (i-1) digits of C, we can put any digit at i’th index.
Hence, dp[i] += (dp[i-1] * n)
c2) For all the Numbers whose first (i-1) digits are same as first (i-1) digits of C, we can only put those digits which are smaller than digit_in_c[i].
Hence , dp[i] += lower[digit_in_c[i]]

Final answer will be dp[B]

For example:

A = [0 1 3 5 7 8], B=1,C=5. 

Initially:

dp = [0 0] 
digits_in_c = [5]
lower = [0 1 2 2 3 3 4 4 5 6 6]

We will always start filling dp from 1st index. Here

dp[1] = dp[1] + lower[digits_in_c[0]]
dp[1] = 0 + lower[5]
dp[1] = 0 + 3 = 3
dp = [0 3]

Answer is dp[B] = dp[1] = 3

A = [1 2 3 4 6 7 8 9], B=3, C=349

Initially:

dp = [0 0 0 0]
digits_in_c = [3 4 9]
lower = [0 0 1 2 3 4 4 5 6 7 8]

for i=1:

dp[1]= dp[0]*n =0
dp[1] = dp[1] + lower[digits_in_c[0]]
dp[1] = 0 + lower[3]
dp[1] = 0 + 2 = 2
dp = [0 2 0 0]

for i=2:

dp[2] = dp[1]*n = 2*3 = 16
dp[2] = dp[1] + lower[digits_in_c[1]]
dp[2] = 16 + lower[4]
dp[2] = 16 + 3 = 19
dp = [0 2 19 0]

for i=3:

dp[3] = dp[2]*n = 19*n = 152
dp[3] = dp[2] + lower[digits_in_c[2]]
dp[3] = 152 + lower[9]
dp[3] = 152 + 7 = 159
dp = [0 2 19 159]

Answer is dp[3] = 159

Time Complexity = O(B).

Solution Code in Python for the above approach

Data Scientist | StoryTeller | Philomath | https://www.linkedin.com/in/priyakoshta