# Problem Definition

## Description

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.

NOTE: All numbers can only have digits from the given set.

Examples:

```plaintext
    Input:
      3 0 1 5
      1
      2
    Output:
      2 (0 and 1 are possible)

    Input:
      4 0 1 2 5
      2
      21
    Output:
      5 (10, 11, 12, 15, 20 are possible)
```

Constraints:

```plaintext
    1 <= B <= 9, 0 <= C <= 1e9 & 0 <= A[i] <= 9
```

## Notes

1. [GitHub - Ilya Ismagilov's solution](https://github.com/ismagilov/interviewbit/blob/84a7b463554b8351db4a6772753b781319cbcc1c/src/math/NumbersOfLengthNAndValueLessThanK.java)

### Solution approach

Let us try to solve for all the possible cases.
Let d be size of A.

* Case 1: If B is greater than length of C or d is 0 then no such number is possible.
* Case 2: If B is smaller than length of C then all the possible combination of digits of length B are valid.

  * Generate all such B digit numbers.
  * For the first position we can't have 0 and for their rest of (B - 1) position we can have all d possible digits.
  * Hence, Answer = d^B if A contains 0 else (d-1) * (d)^(B-1).

* Case 3: If B is equal to length of C

  * Construct digit array of C (call it as digit[]).
  * Let First(i) be a number formed by taking first i digits of it.
  * 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:

  ```plaintext
  First(2) of 423 is 42.
  If  A =  [0, 2] then lower[0] = 0, lower[0] = 0, lower[1]  = 1,  lower[2] = 1, lower[3] = 2
  ```

  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.

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

  1. For all the Numbers whose First (i - 1) is less than First(i-1) of C, we can put any digit at i'th index. Hence, dp[i] += (dp[i-1] * d).
  1. For all the Numbers whose First (i - 1) is same as First(i-1) of C, we can only put those digits which are smaller than digit[i].

  Hence, dp[i] += lower[digit[i]]

  Final answer will be dp[B]

  Remark: For first index don't include 0 if B is not 1 and dp[0] will be 0.

Time Complexity = O(B)