C++ Solution, explained with comments, no dp, case wise solution


#1

int Solution::solve(vector &A, int B, int C) {

stack<int> C_dig;
int temp = C;
while(temp > 0) {
    C_dig.push(temp % 10);
    temp /= 10;
}

// if A is empty
if(A.empty()) {
    return 0;
}

// if no. of digits in C < the required no. of digits B.
if(C_dig.size() < B) {
    return 0; // No number possible
}
    
// if B = 1, 0 can be the first digit, thus seperate case
if(B == 1) {
    int count = 0, i = 0;
    while(A[i] < C && i < A.size()) {
        count++;
        i++;
    }
    return count;
}

// if no. of digits in C > B, then every combination with B digits is possible.
if(C_dig.size() > B) {
    // 0 cannot be the first digit if B > 1
    if(A[0] == 0)
        return (A.size() - 1) * pow(A.size(), B - 1);
    return pow(A.size(), B);
}
    
// Case when no. of digits in C = B

int result = 0;

// Filling one digit at a time starting from left
for(int i = 1; i <= B; i++) {
    int dig = C_dig.top();
    C_dig.pop();
    int count = 0, p = 0;
    // count: to count all digits less that the present digit of C
    // p: to check if present digit of C is in the set A
    for(int j = 0; j < A.size(); j++) {
        if(A[j] < dig) {
            count++;
        }
        if(A[j] == dig) {
            p++;
        }
    }
    if(count == 0 && p == 0 && i == 1) {
        return 0;
    }
    if(A[0] == 0 && i == 1) { // 0 cannot be the first digit
        result += (count - 1) * pow(A.size(), B - i);
    }
    else {
        result += count * pow(A.size(), B - i);
    }
    // if count != 0 but p == 0, then we have to return the result
    // as no other numbers are further possible
    if(p == 0) {
        return result;
    }
}
return result;

}