Solution without DP


#1

int find_all_x_digit_nums(vector A, int B, int count_of_zero) {

int mul = A.size() - (B > 1? count_of_zero: 0), size= A.size();
return mul*pow(size,B-1);

}

int recursive(vector A, int C, int C_len, int count_of_zero, bool first) {

if (C_len == 0)
    return 0;

int digit = C/pow(10, C_len-1);

auto itr_low = lower_bound(A.begin(), A.end(), digit);
bool present = itr_low != A.end() && *itr_low == digit;
if (itr_low == A.end()) {
    int mul = first && C_len > 1? A.size() - count_of_zero: A.size();
    return mul*pow(A.size(), C_len-1);
} else {
    int count_less_than_digit = (itr_low - A.begin()) - (first && C_len > 1? count_of_zero: 0);
    int fixed = count_less_than_digit*pow(A.size(), C_len-1);
    int ten_power = pow(10,C_len-1);
    
    //cout << itr_low - A.begin() << endl;
    //cout << count_less_than_digit << endl;
    //cout << "fixed " << fixed << endl;
    C = C%ten_power;
    //cout<<" C "<<C<<" C_len"<<C_len-1<<endl;
    return fixed + (present? recursive(A, C%ten_power, C_len-1, count_of_zero, false): 0);
}

}

// TODO - Handle integer overflow
int Solution::solve(vector &A, int B, int C) {

int len = 0;
int temp = C;
while (temp) {
    temp/=10;
    len++;
}

if (len < B) 
    return 0;

int count_of_zero = upper_bound(A.begin(), A.end(), 0) - A.begin();

if (len > B) {
    return find_all_x_digit_nums(A, B, count_of_zero);
}

// If len == B
//cout << " C "<<C<<" C_len "<<len<<endl;
return recursive(A, C, len, count_of_zero, true);

}