O(AlogC) solution without DP, took more time to account for edge cases


#1

int Solution::solve(vector &A, int B, int C) {
//decimal to digits
vector digits;
int n = A.size();
if(n==0)
return 0;
int temp = C;
int ans = 0;
while(temp>0){
int rem = temp%10;
digits.push_back(rem);
temp = temp/10;
}

// Reverse the vector cause the way digits are computed
reverse(digits.begin(), digits.end());

if(digits.size()<B)
    return 0;

else if(digits.size()>B){
    if(A[0]==0 && B>1)//NOTE if B == 1 then can use 0 at first pos
        ans = (n-1)*pow(n,B-1);
    else
        ans = pow(n,B);
    
    return ans;
}

else{
    if(A.back()<digits[0]){
        if(A[0]==0 && digits.size()>1)//NOTE if C size == 1 then can use 0 at first pos
            ans = (n-1)*pow(n,B-1);
        else
            ans = pow(n,B);
    
        return ans;
    }
    
    else if(A.front()>digits[0]){// if smallest A no. is bigger than smalles C digit
        return 0;
    }   
        
    vector<int> ind;//to save greater closest index of digits in A
    
    // RUNNING TIME IS O(AlogC)
    for(int i=0;i<digits.size();i++){
        int temp = n;
        for(int j=0;j<n;j++){
            if(A[j]>=digits[i]){//greater closest index
                temp = j;
                break;
            }
        }
        ind.push_back(temp);
    }

    for(int i=0;i<ind.size();i++){
        if(A[0]==0 && i==0 && digits.size()>1)
            ans+= (n-(n-ind[i])-1)*(pow(n,B-(i+1)));
        else
            ans+= (n-(n-ind[i]))*(pow(n,B-(i+1)));
        
        if(A[ind[i]]>digits[i]) // further nos. will be greater than C so break;
            break;
        
        else if(ind[i]==n) //if you encouter an index that allows you to use all nos.
            break;         // then break;
    }
    
    return ans;
}

}