1
00:00:01,560 --> 00:00:02,190
Hi, everyone.

2
00:00:02,220 --> 00:00:08,250
So in this video, I'm going to discuss the minimum steps to win, and you're right, the goal for this

3
00:00:08,250 --> 00:00:08,650
question.

4
00:00:08,850 --> 00:00:10,380
So the question is very simple.

5
00:00:10,410 --> 00:00:14,670
So suppose you are given a value, often looks at the value of any seven month after.

6
00:00:14,680 --> 00:00:20,940
Do you have to reduce the value of N from seven to one and you have to count how many steps you took

7
00:00:21,720 --> 00:00:23,310
and what are the operations allowed?

8
00:00:23,610 --> 00:00:28,270
So basically there are three operations and so the first operation is basically decremental by one.

9
00:00:28,650 --> 00:00:29,430
So what will happen?

10
00:00:29,430 --> 00:00:33,230
You can do and of and buy and equals and minus one.

11
00:00:33,930 --> 00:00:38,880
The second operation allowed is basically you can divide by two, so basically you can do any else and

12
00:00:38,880 --> 00:00:44,270
by two and there's a condition, you can only do it if and only if the number is divisible by two.

13
00:00:44,310 --> 00:00:46,080
So that means the remainder is a zero.

14
00:00:47,060 --> 00:00:50,840
The third operation which is allowed is basically you can divide the number by three.

15
00:00:51,950 --> 00:00:57,680
Now, this operation is only allowed if the given number is divisible by three, so that means the remainder

16
00:00:57,680 --> 00:01:04,310
is zero, but they have to do you have to find the minimum steps from nine to one using these three

17
00:01:04,310 --> 00:01:04,970
operations?

18
00:01:05,030 --> 00:01:07,460
OK, you have to use only these three operations.

19
00:01:08,240 --> 00:01:10,250
So let us take an example to understand it.

20
00:01:11,450 --> 00:01:13,040
So let's say the value of.

21
00:01:14,520 --> 00:01:16,980
So let's see the value of and is seven.

22
00:01:18,930 --> 00:01:25,260
So the first operation is obviously you can discriminate by one, so it will become six, cannot divide

23
00:01:25,260 --> 00:01:25,690
by two.

24
00:01:25,800 --> 00:01:27,550
No can do it by three, no.

25
00:01:28,110 --> 00:01:28,560
So.

26
00:01:29,730 --> 00:01:31,350
Obviously, you can discriminate by one.

27
00:01:31,530 --> 00:01:34,230
So can you divide six by two is six divided by two?

28
00:01:34,230 --> 00:01:34,700
Yes.

29
00:01:34,710 --> 00:01:36,720
So divide by two, it will become three.

30
00:01:37,170 --> 00:01:38,990
So is divisible by three years.

31
00:01:39,000 --> 00:01:40,260
So divide by three.

32
00:01:40,260 --> 00:01:41,250
It will become two.

33
00:01:42,220 --> 00:01:48,370
So obviously, I can divide five, I can recommend one, so it will become four, so it's five days

34
00:01:48,490 --> 00:01:48,880
by two.

35
00:01:48,880 --> 00:01:52,540
No is five by three now, so I can recommend three.

36
00:01:52,540 --> 00:01:53,500
So it will become too.

37
00:01:53,650 --> 00:01:55,260
So estradiol, I don't know.

38
00:01:55,280 --> 00:01:56,880
So estradiol by three.

39
00:01:56,890 --> 00:01:57,340
Yes.

40
00:01:57,700 --> 00:02:00,850
So it will become the second option is divided by three.

41
00:02:00,850 --> 00:02:03,210
So it will become one now for two.

42
00:02:03,550 --> 00:02:05,710
So obviously I can recommend buy one.

43
00:02:06,070 --> 00:02:07,600
So is divisible by two.

44
00:02:07,600 --> 00:02:07,980
Yes.

45
00:02:07,990 --> 00:02:08,979
So divide by two.

46
00:02:09,160 --> 00:02:10,060
It will become one.

47
00:02:10,240 --> 00:02:11,560
So is divisible by three.

48
00:02:11,560 --> 00:02:11,810
No.

49
00:02:11,860 --> 00:02:12,610
So move ahead.

50
00:02:14,130 --> 00:02:20,850
Then for so obviously, I can make it three so four estradiol by twos or divide by two, it will become

51
00:02:20,850 --> 00:02:21,090
to.

52
00:02:22,500 --> 00:02:24,840
Then four is not the celebrity, so move ahead.

53
00:02:25,830 --> 00:02:33,120
So for two, what will happen, I can divide by one so sorry, I can recommend one and also I can divide

54
00:02:33,120 --> 00:02:33,540
by two.

55
00:02:34,410 --> 00:02:38,460
So when and these are all ones, so I will stop here.

56
00:02:39,150 --> 00:02:40,020
I will stop here.

57
00:02:40,320 --> 00:02:41,290
So let's move ahead.

58
00:02:41,310 --> 00:02:43,440
So obviously I can discriminate by one.

59
00:02:43,890 --> 00:02:45,420
I can also divide by three.

60
00:02:45,420 --> 00:02:47,460
So it will become one for two.

61
00:02:47,490 --> 00:02:50,670
I can discriminate one and I can also divide by two.

62
00:02:50,670 --> 00:02:52,590
So it will become one four two.

63
00:02:53,520 --> 00:02:57,900
It will become one, if you will, decrement one, and the second option is divide by two, so it will

64
00:02:57,900 --> 00:02:58,410
become one.

65
00:02:58,960 --> 00:03:03,030
Now, our question is I have to find the minimum number of steps to reach one.

66
00:03:03,450 --> 00:03:04,270
So many missteps.

67
00:03:04,270 --> 00:03:04,890
Steps is basically.

68
00:03:05,860 --> 00:03:06,370
This one.

69
00:03:07,660 --> 00:03:08,770
This is the second step.

70
00:03:09,970 --> 00:03:11,950
And then the third step.

71
00:03:13,180 --> 00:03:15,820
So three steps is Mansour.

72
00:03:16,970 --> 00:03:23,600
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.

73
00:03:24,230 --> 00:03:28,310
There is also one possible solution, if you will go from six to two.

74
00:03:29,670 --> 00:03:31,060
And then you can reach one.

75
00:03:31,410 --> 00:03:37,390
So basically the second option is from seven to six, then from six to two and then go to one.

76
00:03:37,770 --> 00:03:39,850
So there are total three steps.

77
00:03:39,870 --> 00:03:42,030
So one, then two and then three.

78
00:03:42,300 --> 00:03:44,010
So an answer is three steps.

79
00:03:44,010 --> 00:03:45,660
The minimum steps we have to return.

80
00:03:46,020 --> 00:03:49,890
We have to print the minimum number of steps so that we have a step, says three.

81
00:03:51,050 --> 00:03:52,740
So let us take one more example.

82
00:03:53,210 --> 00:04:00,200
So suppose the value of PN is nine, so divided by three, it will become three, then again divided

83
00:04:00,200 --> 00:04:01,530
by three, so it will become one.

84
00:04:01,850 --> 00:04:04,840
So the minimum number of steps in this case is basically two.

85
00:04:05,270 --> 00:04:08,580
So I will return to how we can solve this question.

86
00:04:08,930 --> 00:04:13,340
So basically, many student, so many people will think like this.

87
00:04:13,850 --> 00:04:15,360
You have to convert into one.

88
00:04:15,530 --> 00:04:16,459
And since.

89
00:04:17,399 --> 00:04:22,980
You need to find out the minimum steps, words to invent things and will think of brute force approach,

90
00:04:23,730 --> 00:04:30,690
but brute force approach is so if step one, if the number is divisible by three, then divided by three,

91
00:04:31,420 --> 00:04:34,110
if the number is reduced by two, then divide by two.

92
00:04:34,680 --> 00:04:40,260
Now, if the number is not DL by three, not DL by two, then decrement one, two and minus minus.

93
00:04:40,650 --> 00:04:43,740
So this is a general approach that student will think.

94
00:04:43,750 --> 00:04:45,060
But this approach is wrong.

95
00:04:45,990 --> 00:04:46,500
It is wrong.

96
00:04:46,530 --> 00:04:47,740
Let us take an example.

97
00:04:48,090 --> 00:04:50,100
So let's say the value of an Eastern.

98
00:04:51,300 --> 00:04:56,730
So this brute force approach is first tried to divide by three, so it does not right then try to divide

99
00:04:56,730 --> 00:04:57,120
by two.

100
00:04:57,180 --> 00:04:58,430
Yes, it is divided by two.

101
00:04:58,770 --> 00:05:01,170
So I will go divide by two.

102
00:05:01,170 --> 00:05:02,040
It will become five.

103
00:05:02,400 --> 00:05:03,210
Then again, five.

104
00:05:03,240 --> 00:05:03,840
These are my three.

105
00:05:03,840 --> 00:05:05,250
No way to know.

106
00:05:05,400 --> 00:05:06,510
So and minus minus.

107
00:05:06,720 --> 00:05:09,870
So it will become four again for the while by three.

108
00:05:09,920 --> 00:05:11,160
No four by two.

109
00:05:11,190 --> 00:05:12,810
No three years.

110
00:05:12,810 --> 00:05:13,990
Four is loser by two.

111
00:05:14,010 --> 00:05:15,720
So what I will do, I will divide by two.

112
00:05:16,470 --> 00:05:18,150
Then again to reduce by three.

113
00:05:18,450 --> 00:05:20,240
No to all by two.

114
00:05:20,250 --> 00:05:20,670
Yes.

115
00:05:20,670 --> 00:05:23,130
So you will divide by two and it will become one.

116
00:05:23,310 --> 00:05:24,320
So how many steps.

117
00:05:24,330 --> 00:05:24,870
Step one.

118
00:05:25,260 --> 00:05:27,780
Step two, step three and step four.

119
00:05:27,960 --> 00:05:31,470
So basically you took four steps if you will follow the brute force approach.

120
00:05:32,040 --> 00:05:33,860
Now let us discuss the correct answer.

121
00:05:34,620 --> 00:05:40,200
So if you will follow this brute force approach, your answer came out before the steps came out before.

122
00:05:41,010 --> 00:05:48,570
But there is a shorter and shorter test, which is basically the agreement will then divide by three

123
00:05:48,780 --> 00:05:50,310
and then again divide by three.

124
00:05:50,760 --> 00:05:51,830
So how many steps?

125
00:05:51,840 --> 00:05:53,940
So in this case, I took three steps.

126
00:05:54,570 --> 00:05:56,400
So that means this approach is wrong.

127
00:05:57,000 --> 00:05:58,860
This approach is wrong.

128
00:06:00,370 --> 00:06:02,260
Now let's discuss the correct approach.

129
00:06:04,560 --> 00:06:05,550
So what do you have?

130
00:06:07,020 --> 00:06:09,870
You have a number and there are three possible options.

131
00:06:10,140 --> 00:06:14,880
So the first option is decrease by one by one, so it will become an and minus one.

132
00:06:15,330 --> 00:06:17,700
The second approach is basically divide by two.

133
00:06:18,810 --> 00:06:23,970
And you can only divide by two if the numbers divisible by two and a third approach is basically divide

134
00:06:23,980 --> 00:06:24,420
by three.

135
00:06:24,570 --> 00:06:27,210
Again, if the numbers rule by three, then only.

136
00:06:28,140 --> 00:06:30,720
You can divide by three, so what they will do?

137
00:06:32,260 --> 00:06:38,110
I will tell the commission to find answer for and might listen to the answer is X, then I will tell

138
00:06:38,110 --> 00:06:43,870
variegation find the number of steps for EnVie, two for the number and by two to reach one.

139
00:06:44,080 --> 00:06:45,460
So let's say the answer is way.

140
00:06:46,240 --> 00:06:50,050
Then I will tell recursion to find the answer for converting the number.

141
00:06:50,050 --> 00:06:51,150
And by three to one.

142
00:06:51,220 --> 00:06:54,640
Give me the number of steps for converting and by three to one.

143
00:06:54,790 --> 00:06:56,470
And let's say the answer is Z.

144
00:06:57,600 --> 00:06:58,780
So what to answer?

145
00:06:59,190 --> 00:07:03,960
So finally, my answer will be what I have to do, I have to find out the minimum, so I will take the

146
00:07:03,960 --> 00:07:06,120
minimum of X, Y and Z.

147
00:07:07,150 --> 00:07:08,890
X, Y and Z.

148
00:07:10,160 --> 00:07:16,900
So what is X X is basically the minimum number of steps from converting number and minus one to one,

149
00:07:17,330 --> 00:07:21,160
why is the minimum number of steps for converting the number and by two to one?

150
00:07:21,170 --> 00:07:25,030
And that is the number of steps for converting the number and by three to one.

151
00:07:25,490 --> 00:07:31,010
And since we have to find out the number of steps, I will take a minimum of X, Y and Z and I will

152
00:07:31,010 --> 00:07:37,550
add plus one plus one, because this step for taking this step, I have to add plus one.

153
00:07:37,980 --> 00:07:40,790
OK, so this will be my answer if I will use recursion.

154
00:07:41,450 --> 00:07:43,430
So obviously that equation solution is correct.

155
00:07:43,760 --> 00:07:45,260
OK, recursion will always work.

156
00:07:46,760 --> 00:07:49,250
Now there are three ways of solving this question.

157
00:07:49,260 --> 00:07:51,290
So the first one is using the recursion.

158
00:07:51,830 --> 00:07:54,290
So this one which you will implement yourself.

159
00:07:56,310 --> 00:08:03,120
Now, the second we so what we will do so very cogently and check, so if there is any common problem,

160
00:08:03,270 --> 00:08:07,650
if there is a problem, which we are solving multiple times, so if there is a problem, what we will

161
00:08:07,650 --> 00:08:10,620
do, if that is the case, you will use memorisation.

162
00:08:11,490 --> 00:08:12,690
So what is memorisation?

163
00:08:12,690 --> 00:08:14,640
Memorisation is basically top down DEPI.

164
00:08:16,470 --> 00:08:17,220
Bob, down deep.

165
00:08:17,970 --> 00:08:21,420
What you will do, you will use that occasion approach and you will also take an.

166
00:08:22,370 --> 00:08:25,230
OK, so just like in Fibonacci from right to left and the left.

167
00:08:25,250 --> 00:08:25,470
Right.

168
00:08:25,500 --> 00:08:28,260
So the name of the matter is memorisation.

169
00:08:29,250 --> 00:08:34,620
Now, the third way is if you are able to solve this question using memorisation, then implement the

170
00:08:34,620 --> 00:08:35,549
bottom up DEPI.

171
00:08:37,010 --> 00:08:39,919
So bottom up, Deb, is basically a resolution.

172
00:08:42,580 --> 00:08:48,730
OK, so first, implement the Rickerson, first implement the resolution, the brute force solution,

173
00:08:48,940 --> 00:08:53,040
then check if are overlapping problems a problem which solving multiple times.

174
00:08:53,710 --> 00:08:57,700
So what we can do, we will store so we can use memorisation.

175
00:08:57,970 --> 00:09:02,590
We will store the calculation, we will do the calculation once and we will store the calculation and

176
00:09:02,590 --> 00:09:04,810
we will use this as a result.

177
00:09:05,050 --> 00:09:10,280
So memorisation and if the memory if you can implement memorisation, then implement the bottom up DEPI

178
00:09:10,900 --> 00:09:12,040
the solution.

179
00:09:12,940 --> 00:09:15,640
So I think you can do it, so just give it a try.

180
00:09:16,180 --> 00:09:17,830
I will see you in the next one maybe.