NumbersoflengthNandvaluelessthanK.cpp

/*
Given a set of digits (A) in sorted order, find how many numbers of length B are possible whose value is less than number C.

 NOTE: All numbers can only have digits from the given set. 
Examples:

	Input:
	  0 1 5  
	  1  
	  2  
	Output:  
	  2 (0 and 1 are possible)  

	Input:
	  0 1 2 5  
	  2  
	  21  
	Output:
	  5 (10, 11, 12, 15, 20 are possible)
Constraints:

    1 <= B <= 9, 0 <= C <= 1e9 & 0 <= A[i] <= 9

LINK: https://www.interviewbit.com/problems/numbers-of-length-n-and-value-less-than-k/
*/
vector<int> numToVec(int n){
    vector<int> ret;
    while(n){
        ret.push_back(n%10);
        n = n/10;
    }
    if(ret.size()==0) ret.push_back(0);
    
    reverse(ret.begin(),ret.end());
    return ret;
}

int Solution::solve(vector<int> &A, int B, int C) {
    int n = A.size();
    vector<int> digits = numToVec(C);
    int lenC = digits.size();  
    // ceil(log10(C));
    if(n==0 || B>lenC || B==0) return 0;
    else if(B<lenC){
        if(A[0]==0 && B!=1) return (n-1)*pow(n,B-1);
        else return pow(n,B);
    }else if (B==lenC){
        
        int first;
        vector<int> dp(B+1,0), lower(11,0);
        for(int i = 0;i<n;i++) lower[A[i]+1] = 1; 
        for(int i = 1;i<11;i++) lower[i] += lower[i-1]; 
        
        bool flag = true;
        for(int i = 1; i <= B; i++) {
          int d2 = lower[digit[i-1]];
          dp[i] = dp[i-1] * n;
        
          // For first index we can't use 0
         if(i == 1 &&  A[0] == 0 && B != 1)
             d2 = d2 - 1;
        
         //Whether (i-1) digit of generated number can be equal to (i - 1) digit of C.
         if(flag)
             dp[i] += d2;
         //Is digit[i - 1] present in A ?
            flag = flag & (lower[digit[i-1] + 1] == lower[digit[i-1]] + 1);
        }
        return dp[B];   
    }
    
    
    
}


// int Solution::solve(vector<int> &A, int B, int C) {
//     int n = A.size();
//     long long int count = 0;
//     int i_digit, i;
//     if(n <=0) return 0;
//     if(n==1){
//         if(A[0]<C && B==1){
//             return 1;
//         }
//     }
   
//     for(int j = 0; j < B; j++){
//     i_digit = (int)(C/(pow(10,B-1-j)))%10;
//     // cout << i_digit << endl;
//     for(i = 0; A[i]<i_digit; i++);
//         // cout << i << endl;

//     if(A[0] == 0 && i >0 && B != 1){
//         i--;}
//     //   count += (i-1)*(B-j) + (i-1)*(B-j-1);  
//     // } else{
   
//     count += (B-j-1)*n*i;
//     // }
//     // cout<<count<< endl;
//     }
    
    
//     return (int)count;
// }


/*
Hint:


Let us try to solve for all the possible cases.
Let d be size of A.

Case 1: If B is greater than length of C or d is 0 then no such number is possible.

Case 2: If B is smaller than length of C then all the possible combination of digits of length B are valid.

Generate all such B digit numbers.
For the first position we can’t have 0 and for ther rest of (B - 1) position we can have all d possible digits.
Hence, Answer = d B if A contains 0 else (d-1) * ( d )(B-1)

Case 3: If B is equal to length of C
Construct digit array of C ( call it as digit[]).

Let First(i) be a number formed by taking first i digits of it.
Let lower[i] denote number of elements in A which are smaller than i.
It can be easily computed by idea similar to prefix sum.

For example:

First(2) of 423 is 42. 
If  A =  [ 0, 2] then lower[0] = 0, lower[0] = 0, lower[1]  = 1,  lower[2] = 1, lower[3] = 2  
Generate B digit numbers by dynamic programming. Let say dp[i] denotes the total numbers of length i which are less than first i digits of C.

Elements in dp[i] can be generated by two cases :

i) For all the Numbers whose First(i - 1) is less than First (i-1) of C, we can put any digit at i’th index.
Hence, dp[i] += (dp[i-1] * d)

ii) For all the Numbers whose First (i - 1) is same as First (i - 1) of C, we can only put those digits which are smaller than digit[i] .

Hence , dp[i] += lower[digit[i]]

Final answer will be dp[B]

Remark:
For first index don’t include 0 if B is not 1 and dp[0] will be 0.

Time Complexity = O(B)

*/