Given an array of digits which is sorted in non-decreasing order. You can write numbers using each digits[i] as many times as we want. For example, if digits = ['1','3','5'], we may write numbers such as '13', '551', and '1351315'.

Return the number of positive integers that can be generated that are less than or equal to a given integer n.

&nbsp;
Example 1:

Input: digits = ["1","3","5","7"], n = 100
Output: 20
Explanation: 
The 20 numbers that can be written are:
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.


Example 2:

Input: digits = ["1","4","9"], n = 1000000000
Output: 29523
Explanation: 
We can write 3 one digit numbers, 9 two digit numbers, 27 three digit numbers,
81 four digit numbers, 243 five digit numbers, 729 six digit numbers,
2187 seven digit numbers, 6561 eight digit numbers, and 19683 nine digit numbers.
In total, this is 29523 integers that can be written using the digits array.


Example 3:

Input: digits = ["7"], n = 8
Output: 1


&nbsp;
Constraints:


	1 &lt;= digits.length &lt;= 9
	digits[i].length == 1
	digits[i] is a digit from&nbsp;'1'&nbsp;to '9'.
	All the values in&nbsp;digits are unique.
	digits is sorted in&nbsp;non-decreasing order.
	1 &lt;= n &lt;= 109


class Solution():
    def atMostNGivenDigitSet(self, digits, n):
        cache = {}
        target = str(n)

        def helper(idx, isBoundary, isZero):
            if idx == len(target): return 1
            if (idx, isBoundary, isZero) in cache: return cache[(idx, isBoundary, isZero)]
            
            res = 0
            if isZero and idx != len(target)-1:
                res+= helper(idx+1, False, True)
            for digit in digits:
                if isBoundary and int(digit) > int(target[idx]): continue
                res+= helper(idx+1, True if isBoundary and digit == target[idx] else False, False)

            cache[(idx, isBoundary, isZero)] = res
            return res

        return helper(0, True, True)
class Solution {
    
    
    // DIGIT DP IS LOVE 
    Integer[][][] digitdp;
    public int solve(String num, int pos, boolean bound, Integer[] dig,boolean lead) {

        if (pos == num.length()) {
            return 1;
        }

        int maxDigit = -1;
        
        if(digitdp[pos][(bound==true)?1:0][(lead==true)?1:0] !=null) return digitdp[pos][(bound==true)?1:0][(lead==true)?1:0];

        if (bound) {
            maxDigit = num.charAt(pos) - '0';
        } else {
            maxDigit = 9;
        }

        int ans = 0;
        for (int i = 0; i <=maxDigit; i++) {
            
            // 0 can only be leading 
            if(i==0 && lead){

                ans += solve(num,pos+1,false,dig,lead);
                
            }else{
                
              int res =  Arrays.binarySearch(dig,i);

              if(res>=0){
                 // lead = false; // now it is not possible to 0 to be in lead any more once any other call has been made
                 ans += solve(num, pos + 1, bound & (i == num.charAt(pos)-'0'), dig,false);
              }
                
            }
        }

        return digitdp[pos][(bound==true)?1:0][(lead==true)?1:0] = ans;

    }

    public int atMostNGivenDigitSet(String[] digits, int n) {

        String num = n + "";
        Integer[] dig = new Integer[digits.length];
        for(int i=0;i<dig.length;i++){
            dig[i] = Integer.parseInt(digits[i]);
        }
        
        digitdp = new Integer[20][2][2];
        return solve(num, 0, true, dig,true)-1;
    }
}
class Solution {
public:

    using ll = long long;

    int countLen(int n) {
        int cnt = 0;
        while(n) {
            cnt++;
            n /= 10;
        }
        return cnt;
    }

    vector<int>getDigits(int n) {
        vector<int>digits;
        while(n) {
            digits.push_back(n % 10);
            n /= 10;
        }

        reverse(digits.begin(), digits.end());
        return digits;
    }


    int solve(int idx, bool flag, vector<int>&digits, vector<int>&number) {
        if(!flag) {
            int res = 1;
            for(int i = idx; i<number.size(); i++) {
                res *= digits.size();
            }
            return res;
        }


        if(idx >= number.size()) return 1;

        int curr = 0;

        for(int dig: digits) {
            if(dig < number[idx]) {
                curr += solve(idx + 1, false, digits, number);
            } else if(dig == number[idx]) {
                curr += solve(idx + 1, true, digits, number);
            } else break;
        }

        return curr;
    }


    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        int len = countLen(n);
        vector<int>nums;
        for(string str: digits) {
            nums.push_back(stoi(str));
        }
        sort(nums.begin(), nums.end());
        ll res = 0;
        
        
        for(int i = 1; i<len; i++) {
            int curr = 1;
            bool flag = false;
            for(int j = 0; j<i; j++) {
                flag = true;
                curr *= (int)digits.size();
            }
            if(flag)
                res += curr;
        }

        vector<int>number = getDigits(n);
        
        res += solve(0, true, nums, number);

        return res;

    }
};
var atMostNGivenDigitSet = function(digits, n) {
    const asString = ""+ n;
    let smaller = 0;
    let prev = 1;
    for (let i = asString.length - 1; i >= 0; --i) {
        const L = asString.length - 1 - i;
        const num = +asString[i];
        let equal = 0;
        let less = 0;
        for (let digit of digits) {
            if (digit == num) {
                equal = 1;
            }
            if (digit > num) {
                break;
            }
            if (digit < num) {
                less++;
            }
        }
        prev = (less * Math.pow(digits.length, L)) + equal * prev;
        if (L < asString.length - 1) {
            smaller += Math.pow(digits.length, L + 1);
        }
    }
    return smaller + prev;
};
Numbers At Most N Given Digit Set