Intuitive recursive solution O(A log(C))


#1

Honestly this one took me a while, because of all the edge cases. I found the provided solution to be a little unfair, as it employs dynamic programming which is a locked topic for most people at this point. Here’s my passing solution that uses a more intuitive approach than the answer. I believe the runtime is O(A log©) as worst case you need to run through every digit of C (which is proportional to the log10(C)) and every number in the list A.

I ended up making another function to account for the special when you’re at the first digit.

The initial bits are the straightforward, look at B and solve the base cases when B < len(C) and B > len(C). The hard part is what to do with B == C.

There are three cases:

  1. The current number is less than the first digit of C. In this case, this digit can precede all the others. We have to check earlier on if we’re allowed to include zero in this.
  2. There’s the case when the current number is equal to the first digit of C. In this case we have further options:
  • If there’s only a single digit, then pass - we can’t use this number
  • Otherwise recurse, and solve for C[1: ] and B is the length of the new C (without leading zeros)
  • In the case when C[1:] contains a zero, but A doesn’t, then there are no solutions. So a simple check for this is if A[0] == 0, solve C[1:], B-1 otherwise solve C[1:], len(C[1:]).
  1. Otherwise the number is greater, pass

Hope this helps, good luck!

int solve_b(vector<int> &A, int B, int C, bool first_digit=false) {
    
    if (C <= 0 || B <= 0 || A.size() == 0)
        return 0;
    
    string rep = to_string(C);
    int max_number = rep.at(0) - '0';
    
    if(B < rep.size()){
        if(A.front() == 0 && B > 1)
            return (A.size() - 1) * pow( A.size(), B-1 );
        else
            return pow( A.size() , B);
    }
    else if (B > rep.size())
        return 0;
    else{
        int count = 0;
        
        for(auto a : A){
            
            if(a == 0 && first_digit && rep.size() > 1) continue;
            
            if(a < max_number){
                count += pow( A.size(), rep.size() - 1);
            }else if(a == max_number){
                if(rep.size() == 1) continue;
                
                int new_c = stoi(rep.substr(1));
                
                if(A.front() != 0){
                    count += solve_b(A, B-1, new_c, false);
                }else{
                    count += solve_b(A, to_string(new_c).size(), new_c, false);
                }
                
            }
        }
        
        return count;
    }
}

int Solution::solve(vector<int> &A, int B, int C) {
    return solve_b(A, B, C, true);
}

#2

Hi. Could you kindly tell me why you are calling solve_b(A, B-1, new_c, false), solve_b(A, to_string(new_c).size(), new_c, false) separetely for when A.front()!=0 and A.front()==0. I really can’t wrap my head around the reason. isn’t B-1 and to_string(new_c).size() same ? I know I am wrong because your solution works but if you could please help me understand why you are passing B-1 and to_string(new_c).size() respectively I would really be grateful.


#3

It’s been a while, and to be frank I can’t remember. Here’s what I think is going on.

Any time C has a zero (at least) in the second position, and B == len(C), then len(substr(C, 1)) != B-1. I’ll try and run through an example.

Eg you have C=2015 and A=123, B=4.

When you get to a=2. If can use 0 then you have all the 2 digit solutions up to 15. In this example, if you can’t use zero then there are no solutions (and when you recurse, you’ll hit that case). You can’t use B-1 here.

But actually you can replace that entire condition with just the second case and it’ll still work.

count += solve_b(A, to_string(new_c).size(), new_c, false);

#4

Your solution is very good to understand as I am not familiar with DP.
You said replacing entire condition with :

count += solve_b(A, to_string(new_c).size(), new_c, false);

should work but its not working?