Simplest lightweight solution in C++ using recursion without DP


#1

void recur(vector &arr, int b, string &c, int k, bool flag, int &cnt){
if(b==0)
return;
int i = flag?1:0, n = arr.size();
while(i<n){
if(arr[i]<(c[k]-‘0’))
cnt+=pow(n,b-1);
else{
if(arr[i]==(c[k]-‘0’))
recur(arr,b-1,c,k+1,false,cnt);
return;
}
i++;
}
}

int Solution::solve(vector &A, int B, int C) {
string c = to_string( C );
if(B>c.length() || B==0 || A.size()==0)
return 0;
bool flag = (A[0]==0 && B>1);
if(B<c.length())
return (flag)?pow(A.size(),B-1)*(A.size()-1):pow(A.size(),B);
int cnt=0;
recur(A,B,c,0,flag,cnt);
return cnt;
}