Hi, everyone.
So in this video, I'm going to discuss the minimum steps to win, and you're right, the goal for this
question.
So the question is very simple.
So suppose you are given a value, often looks at the value of any seven month after.
Do you have to reduce the value of N from seven to one and you have to count how many steps you took
and what are the operations allowed?
So basically there are three operations and so the first operation is basically decremental by one.
So what will happen?
You can do and of and buy and equals and minus one.
The second operation allowed is basically you can divide by two, so basically you can do any else and
by two and there's a condition, you can only do it if and only if the number is divisible by two.
So that means the remainder is a zero.
The third operation which is allowed is basically you can divide the number by three.
Now, this operation is only allowed if the given number is divisible by three, so that means the remainder
is zero, but they have to do you have to find the minimum steps from nine to one using these three
operations?
OK, you have to use only these three operations.
So let us take an example to understand it.
So let's say the value of.
So let's see the value of and is seven.
So the first operation is obviously you can discriminate by one, so it will become six, cannot divide
by two.
No can do it by three, no.
So.
Obviously, you can discriminate by one.
So can you divide six by two is six divided by two?
Yes.
So divide by two, it will become three.
So is divisible by three years.
So divide by three.
It will become two.
So obviously, I can divide five, I can recommend one, so it will become four, so it's five days
by two.
No is five by three now, so I can recommend three.
So it will become too.
So estradiol, I don't know.
So estradiol by three.
Yes.
So it will become the second option is divided by three.
So it will become one now for two.
So obviously I can recommend buy one.
So is divisible by two.
Yes.
So divide by two.
It will become one.
So is divisible by three.
No.
So move ahead.
Then for so obviously, I can make it three so four estradiol by twos or divide by two, it will become
to.
Then four is not the celebrity, so move ahead.
So for two, what will happen, I can divide by one so sorry, I can recommend one and also I can divide
by two.
So when and these are all ones, so I will stop here.
I will stop here.
So let's move ahead.
So obviously I can discriminate by one.
I can also divide by three.
So it will become one for two.
I can discriminate one and I can also divide by two.
So it will become one four two.
It will become one, if you will, decrement one, and the second option is divide by two, so it will
become one.
Now, our question is I have to find the minimum number of steps to reach one.
So many missteps.
Steps is basically.
This one.
This is the second step.
And then the third step.
So three steps is Mansour.
So I will go from seven to six, then I will go from six to three and then I will go from three to one.
There is also one possible solution, if you will go from six to two.
And then you can reach one.
So basically the second option is from seven to six, then from six to two and then go to one.
So there are total three steps.
So one, then two and then three.
So an answer is three steps.
The minimum steps we have to return.
We have to print the minimum number of steps so that we have a step, says three.
So let us take one more example.
So suppose the value of PN is nine, so divided by three, it will become three, then again divided
by three, so it will become one.
So the minimum number of steps in this case is basically two.
So I will return to how we can solve this question.
So basically, many student, so many people will think like this.
You have to convert into one.
And since.
You need to find out the minimum steps, words to invent things and will think of brute force approach,
but brute force approach is so if step one, if the number is divisible by three, then divided by three,
if the number is reduced by two, then divide by two.
Now, if the number is not DL by three, not DL by two, then decrement one, two and minus minus.
So this is a general approach that student will think.
But this approach is wrong.
It is wrong.
Let us take an example.
So let's say the value of an Eastern.
So this brute force approach is first tried to divide by three, so it does not right then try to divide
by two.
Yes, it is divided by two.
So I will go divide by two.
It will become five.
Then again, five.
These are my three.
No way to know.
So and minus minus.
So it will become four again for the while by three.
No four by two.
No three years.
Four is loser by two.
So what I will do, I will divide by two.
Then again to reduce by three.
No to all by two.
Yes.
So you will divide by two and it will become one.
So how many steps.
Step one.
Step two, step three and step four.
So basically you took four steps if you will follow the brute force approach.
Now let us discuss the correct answer.
So if you will follow this brute force approach, your answer came out before the steps came out before.
But there is a shorter and shorter test, which is basically the agreement will then divide by three
and then again divide by three.
So how many steps?
So in this case, I took three steps.
So that means this approach is wrong.
This approach is wrong.
Now let's discuss the correct approach.
So what do you have?
You have a number and there are three possible options.
So the first option is decrease by one by one, so it will become an and minus one.
The second approach is basically divide by two.
And you can only divide by two if the numbers divisible by two and a third approach is basically divide
by three.
Again, if the numbers rule by three, then only.
You can divide by three, so what they will do?
I will tell the commission to find answer for and might listen to the answer is X, then I will tell
variegation find the number of steps for EnVie, two for the number and by two to reach one.
So let's say the answer is way.
Then I will tell recursion to find the answer for converting the number.
And by three to one.
Give me the number of steps for converting and by three to one.
And let's say the answer is Z.
So what to answer?
So finally, my answer will be what I have to do, I have to find out the minimum, so I will take the
minimum of X, Y and Z.
X, Y and Z.
So what is X X is basically the minimum number of steps from converting number and minus one to one,
why is the minimum number of steps for converting the number and by two to one?
And that is the number of steps for converting the number and by three to one.
And since we have to find out the number of steps, I will take a minimum of X, Y and Z and I will
add plus one plus one, because this step for taking this step, I have to add plus one.
OK, so this will be my answer if I will use recursion.
So obviously that equation solution is correct.
OK, recursion will always work.
Now there are three ways of solving this question.
So the first one is using the recursion.
So this one which you will implement yourself.
Now, the second we so what we will do so very cogently and check, so if there is any common problem,
if there is a problem, which we are solving multiple times, so if there is a problem, what we will
do, if that is the case, you will use memorisation.
So what is memorisation?
Memorisation is basically top down DEPI.
Bob, down deep.
What you will do, you will use that occasion approach and you will also take an.
OK, so just like in Fibonacci from right to left and the left.
Right.
So the name of the matter is memorisation.
Now, the third way is if you are able to solve this question using memorisation, then implement the
bottom up DEPI.
So bottom up, Deb, is basically a resolution.
OK, so first, implement the Rickerson, first implement the resolution, the brute force solution,
then check if are overlapping problems a problem which solving multiple times.
So what we can do, we will store so we can use memorisation.
We will store the calculation, we will do the calculation once and we will store the calculation and
we will use this as a result.
So memorisation and if the memory if you can implement memorisation, then implement the bottom up DEPI
the solution.
So I think you can do it, so just give it a try.
I will see you in the next one maybe.