1235. Numbers at Most N Given Digit Set

Given a sorted set of distinct non-zero digit characters and an integer n, count the positive integers that can be written using only those digits (with repetition allowed) and are less than or equal to n. The input is JSON {digits, n}.

Input: JSON {digits, n}.

Output: Integer — the count of writable numbers at most n.

Examples

Input: {"digits":["1","3","5","7"],"n":100}
Output: 20
Explanation: Four 1-digit and sixteen 2-digit numbers.

Input: {"digits":["1","4","9"],"n":1000000000}
Output: 29523
Explanation: Counting all shorter lengths plus matches.

Input: {"digits":["7"],"n":8}
Output: 1
Explanation: Only 7.

Constraints

• 1<=|digits|<=9
• 1<=n<=10^9

Asked by