Hello, everyone.
So in this video, what we are going to discuss, we are going to discuss how we can reduce the time
and space complexity for this problem.
So I already give you a hint that we can use the mathematical approach to reduce time and space complexity.
And the problem and the solution that we are going to discuss today is very, very important because
many times in ask this problem that can introduce time into space complexity for this.
And if you haven't seen this video, then it will be really, really difficult for you to solve this
problem in an interview.
So let's discuss the problem.
Let's discuss the solution basically.
So we are provided with McCrossin Matrix.
And how many steps we can take downward so we can take em minus one down steps.
Right, and we can take and minus one right steps basically moving in the right direction, right to
reach the end point, I'm repeating myself, AM metrics is given to us.
We want to reach an endpoint so far reaching the end point.
We are going to take minus one down step and and minus one right step simple right down step.
I am representing my ID and right step.
I am representing by our knowledge.
Please hear my statement carefully.
All the combination, all the permutations of M minus one down steps and and minus one right steps will
reach the end point.
I'm repeating myself all the combination, all the permutation of M minus one down step and N minus
R right step will reach the end point.
It does not matter when you take right step or when you take down step right.
It doesn't matter.
I'm repeating myself.
It doesn't matter when you take right step or when you don't step, because ultimately the total number
of steps downward will be minus one and the total number of steps right where it will be and minus one.
So permutation is.
So what will be the permutation?
We need to take down steps.
How many down steps and minus one times and we are going to take right steps, how many times that I
step and the minus one times.
So the formula for this is basically minus one plus and minus one.
Factorial divided by M minus one factorial.
And minus one Victorian, so this is the formula.
This is the permutation formula.
Now, let's simplify this formula a little bit.
So if Multiemployer begins C minus and minus one, it will become minus two.
So M plus and minus two factorial divided by M minus one factorial and minus one factorial.
So this is our answer.
This is the unique possible part, this is our answer, right?
And now let's see how we can simplify this.
So I'm writing the formula once again, so our answer is basically M plus and minus two factorial.
Divided by and minus one factorial and and a minus one factorial.
Now let's simplify this.
So can I write it like this?
One, two, three, four and so on and minus one.
Then and these are all multiplication, right?
These are all multiplications.
Then it will be and plus one, then it will be an two and so on till and plus minus two.
So I can write numerator like this and how can I write the denominator?
So denominator will be.
And minus on Vectorial.
And N minus one Victorian, right, this is the denominator and if we can see so this and minus one
factorial will cancel out this part.
Right.
This is basically tell this we have in mind this on Vectorial, so now what is our enumerator numerators
and.
And plus one.
And to.
And plus minus two, and what is our denominator, so our denominator is simply minus one factorial,
which is nothing but one, two, three, four till M minus one.
OK, so this is M minus one factorial starting from one till M minus one.
So this is our answer.
So how many?
Values are present, how many values are present in the numerator so.
These are basically M minus one Tumbes.
In the numerator, we have M minus one times and in the denominator also we have minus Wyndham's.
So this is our answer.
We have the value of N and we also have the value of him.
We just need to find out this value and that will be our answer.
So let me write it clearly here and then I will write the code.
So our answer is basically an.
And plus one and plus two, and it will go on daily and plus and minus two.
And in the denominator we have when we have two, we have three and it will go up to last and will be
minus one.
So this is our formula and now it's very simple gold.
So let's just start writing the code.
The code is going to be very, very simple.
So first, let's comment about this code.
OK, so what we need to do.
Let's take a very long, long answer, very long, long, because we are multiplying so they may overflow.
So to avoid stack overflow, so to avoid integer overflow, let's take long, long instead of integer.
Now, what do we need?
We need a for loop.
And this for loop will start with.
And you can see I'm starting with N and I need to go to Bill and plus and minus two so I will start
from M..
I will go till end plus M minus to find.
I placeless and what we need to do, so our answer will be the correct answer, multiply and answer,
you will be the correct answer divided by you can see here we are dividing by one, two, three delamination.
So we will divide by a minus and plus one.
So how I figured out this value, so it's very simple, so for and I want to divide by one, right.
So the value of AI is basically and so forth, then I want to divide by one.
So the put the value of equals and so and minus and plus one it will become one right.
When the value of five will become and plus one.
So when the value of AI is and plus one this value will become an minus and plus one.
So this will become to.
OK, so I'm doing like this for you, I will divide by three and so on.
Separate whenever I become and plus and minus two and plus and minus two, what disvalue will become.
So put the value of I and plus and minus two and this is minus N plus one.
So minus in this, this is minus two degrees plus and minus one.
So this will become M minus denominate.
Right.
So this logic is correct.
And now what we need to do, simple, we just need to return our answer.
We simply need to return our answer, but as you can see here, the return type is integer and the return
type of answer variable is basically longlong.
So let's typecast and then we will return.
So now let's try to submit our code and let's see whether it will work or not.
Yeah, so basically our solution is working and now let us try to find out the time and the space complexity
for the solution, so as we can see, we are not using any extra space.
So the space complexity is basically big off when and what is the time complexity.
So we are just iterating.
And how many times are there M minus one comes out there.
So time, complexity, we can say big off and minus and all we can save time.
Complexity is basically big of M.
Right.
So what we can do, so suppose if the value of em is much, much, much, much good then and then instead
of this formula so we can sell and minus one factorial, if you remember.
So instead of cancelling and minus unfactual, I will cancel M minus on Vectorial.
So here you can write one check, you can write if health condition.
So if the value of M is good then nd then this solution.
Sorry if the value of.
So I decided.
So if the value of N is guerdon M then the solution is correct.
Otherwise you need to cancel M minus and then you can modify this code.
So basically instead of writing big arfin, what I will do, I will write big off minimum of M comma
and.
I'm repeating myself so far, this code, the code that I have written, the time complexities big off
em, but what is the improvisation?
What is the improvement that I am suggesting is so it can happen and is much, much lower than.
And then in that case, if you remember in bulk and reading the formula I was canceling and minus one
factorial.
So if this is the case, then you will cancel and minus one factorial.
Similarly, your formula will change and your code will also change.
So that's why I am writing that after improving the school, our time complexity will become big of
a minimum of M and then so you can see our time complexities linear.
Our time complexity is linear and space complexity is basically constant, so our algorithm has become
very, very optimized.
So this court is really, really optimized as compared to our previous code.
And I suggest you watching this video before you go for an interview, because many times you will be
able to give this approach.
But we will say give me a better approach and this is the better approach, a mathematical approach.
So this is it from this video.
Guys, I will see you in the next one.
Thank you.