# 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

349Output1:159Input2:0 1 2 3 5 6

1

5Output2: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 **

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

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 Cc2= 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 = [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