# 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 93349Output1:159Input2:0 1 2 3 5 615Output2: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, lower = 1, lower = 1, lower = 2, lower =2 and lower = 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 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 Cdp[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 = lower = [0 1 2 2 3 3 4 4 5 6 6]`

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

`dp = dp + lower[digits_in_c]dp = 0 + lowerdp = 0 + 3 = 3dp = [0 3]`

Answer is dp[B] = dp = 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= dp*n =0dp = dp + lower[digits_in_c]dp = 0 + lowerdp = 0 + 2 = 2dp = [0 2 0 0]`

for i=2:

`dp = dp*n = 2*3 = 16dp = dp + lower[digits_in_c]dp = 16 + lowerdp = 16 + 3 = 19dp = [0 2 19 0]`

for i=3:

`dp = dp*n = 19*n = 152dp = dp + lower[digits_in_c]dp = 152 + lowerdp = 152 + 7 = 159dp = [0 2 19 159]`

Time Complexity = `O(B).`