Hello everyone and welcome back.
So now we are going to continue our discussion and solve this question, which I gave to you in the
last video.
The question actually asks you to find the number of digits which are given in a particular, let's
say, number.
So the again the examples one, two, three.
It has three digits, right?
Uh, on that note, uh, one very good thing is to uh, whenever, whenever you are given these type
of question is to think of all the possible use cases and try to write them once as well.
Right.
So now let us solve this question.
First of all, let us see how the recurrence relation is going to look like okay.
So recurrence relation actually is going to something like this.
Uh now if uh let us think of this intuitively first.
Right.
So if you can tell me okay.
If I let's say just make my number little small.
So right now I'm dealing with say one, 231 second.
Yeah.
So now right now I'm dealing with let's say one, two, three.
If I am able to tell you if I am able to tell you that, okay, I know the last digit is going to count
to one.
And that is of course going to be true.
And you found for all the other digits which are left.
So this number can be so big, you don't need to care about anything.
Right.
This number can be any any metric.
So let's say even if you're dealing with this many number right.
So let's say 31584395.
You can just handle the last digit right.
You know that okay.
This digit is going to be one.
And you can ask your recursion to give you the answer for this.
Okay.
So that is what how we solve the question.
That is the mentality which I want all of you to actually think of how exactly to solve them.
So now if you see this, let's say if I have something like this, then what the recursion relation
is going to be like.
So I can say that the number of digits okay, number of or let me just call this function directly okay.
So digit in 123 is going to be something like one plus digit and one two.
Right.
So I can just directly write this thing everyone.
Because of which if you give me the answer for this, this is a smaller problem which I have to actually
get the answer for, and then I can solve for my bigger problem.
Right?
So we have found a recursion A recursion relationship.
Everyone.
Recurrence relation.
And if I have to make a tree.
If I have to make a tree, then that's also going to be a lot easy.
So it's going to be one, two, three.
This is going to get called for one two.
And now this is going to get called for one.
Now I have to of course think for a base condition and everything.
So let's now work on that.
The base condition I think, which will work very nice for this particular question, is that if we
have a number which is, let's say from 1 to 9, I can return one as an answer depending on platform
and the question zero.
We can see that if you have to return one for zero, or I would say zero, like if you have to take
this as a number or not, because a small I would say caveat in this particular question is that let's
say if you have a number nine, okay.
So you're going to call for now either you can treat this as a base case, which I'm going to do, or
let's say you do.
You basically try to reduce it further and you're going to get zero okay.
So we are going to see how we can reduce it though we have done previous questions where I've already
given you an idea that how we reduce the numbers from starting or to end.
Now, when you reduce it okay, you are going to get zero.
So you have to make sure that either this is returning 0 or 1.
Based on that logic only you are working on writing your code down.
Okay, so let us solve this everyone.
Now let us try to solve this now the way we can reduce our number, right.
The way we can reduce our number that is actually something like this, which I think we have already
discussed lots of time.
So let's say if I have some number one, two, three, if I divide it by ten, right, I'm going to
get 12.3.
And I cannot take it as an integer directly.
Right.
So if I take this as an integer, let me just do take all of this as an integer.
So if I typecast it as an integer, I'm going to get my answer as 12.
Okay.
So let me just write this code and then I think it will be a lot more clear.
So if let's say if I'm saying my n is greater than equal to one and n is less than equal to nine, okay,
then I know then I always know that the answer is one.
So I can directly return the answer for the use case of zero, I am taking the answer as zero.
Now if it is one as well, you can just do it as one and you your cases will be handled Just that you
have to make sure.
You have to make sure.
And I'm going to show you exactly why you have to make sure.
So let us take it one.
And I'm going to show you the problem if we take it as one.
Right.
If let's say you take this just as your overall, uh, I would say test case, then what the problem
is going to be.
Okay.
And these are some caveat or something which you have to, uh, handle whenever you are doing recursion
question.
Because if you remember in PMI, the overall I would say work of proving the test case actually falls
on us right in the some question as well.
In PMI, we solve that question and came to the answer.
Now let's say okay.
Now the next thing is that I will be getting a number okay.
So I have to get a small answer okay.
So my small answer for that I have to first make small number.
Now the way I can make this small number is something like this.
Integer of n divided by ten.
Now why is that the case?
Let us quickly understand this as once as well.
So let me just comment this whole code.
Uh, let's say if my A is 99, let's say one, two, three, right.
If I print a 8%.
Eight divided by ten and let me run this thing.
You are getting 12.3, right?
So what effectively this is helping me do.
Now this is of course going to be 123412334.5.
But if I just type this to an integer then I'm going to get my number one second.
Yeah.
Then I'm going to get my number where the last digit is going to get removed.
Right.
So we take the percentage to get the last digit.
And to remove the last digit, you can just directly call on this number like this.
So I know now I know that let me just remove this.
Now I know that my last digit right.
The last digit which I have, it's going to basically come to a or basically it's going to contribute
one to the answer for the other thing, I can just call this code or small answer small number.
Yeah, I can call this directly.
And once I get my answer is just going to be one plus small answer.
Now I don't want to quotient this as of now.
And I think this is very much clear why I don't want to do that.
And you can just return your answer.
Okay.
So just to prove that okay, why this is a wrong base case, let me just Solve.
Call it for nine and you will understand that the answer is going to be wrong.
Okay, so answer is coming out to be true.
The reason for that, I hope all of you understand that.
The reason for that effectively is that we would have called for nine initially.
We would have called that I am taking is a ditch function for nine.
This nine now would have been actually reduced to zero where our base case comes and kicks in.
Now this returns one and post this.
I am returning two after adding this one again, right?
So I am adding this one again.
So for zero it will be returning from here.
I will get my small number as zero, small answer as one.
And the final answer I am going to make is going to be two, and I am going to return two here.
Okay, so this is a wrong base case.
Like just this is not the base case which we should be thinking in terms of the right base case is actually
if n is greater than or equal to one and n less than or equal to nine, then I am going to return one
zero.
As I said, you can just see for where you are solving this code.
If it is asking you to solve by zero.
If you even ask in the interview, interviewer, just ask an interviewer that, hey, what do you want
me to do for n is equal to zero?
Is do I have to count it as one or not?
In a real sense, I think yes, we can leave it as it is because it's going to be one.
But yes, we have to make sure that we avoid this kind of a kill.
So we always include this base case as well.
Okay.
So because for all the base case we have to handle this thing, recursion is not going to handle that
for us.
Recursion will do this work.
Small work.
You don't have to do anything.
You can just assume that everything is going to be fine.
And yeah, I think this works as better as any code and you will be getting an answer, right?
So let me run this for all of you.
I think it's not saved.
Yeah.
One three and six okay.
So let's let us quickly just see this in Python tutorial as well everyone.
So I think it's pretty straightforward.
But then again I want to make sure that you understand the full understanding.
So see when this function first gets defined.
And then we are going to call for nine.
Nine is a very easy and simple base case.
So we are just going to return from three.
And we are going to get our answer.
That is one.
When we go for one, two, three okay.
First it's going to check for both the base condition.
And that's of course not the answer.
Small number.
Not pay attention to small number.
It's going to be 12 because I have typecast it into integer.
Now for my small answer, I'm going to make another call here.
Now 12 is going in.
And again, that's not going to fall into any of the base cases.
So I'm going to call out recursion.
Now let us see.
Small number is going to be one.
This time it's going to get called.
We are going to get the answer as one.
These functions are still waiting in the stack.
They will get removed once they have finished their execution.
I got the answer as one.
So my this 12 one.
This can now return two as an answer.
And now the next one it can actually return three as an answer.
Okay.
So this I hope it helps.
Now of course for zero if answer is one then also you here also you're going to get the answer is one
only for zero right?
So great everyone I hope this is clear.
Now in the next class we are going to do another question.
And now I'm going to, I would say notch things up a little.
So we are going to do where multiple cases can be there, we are going to learn or I would say do a
very important and famous question again, the Fibonacci number.
So let us start that in the next class.
And yeah, thanks.
And let's meet in the next class.
Thank you everyone.