1
00:00:01,110 --> 00:00:02,040
Hello, everyone.

2
00:00:02,190 --> 00:00:06,720
So in this video, what we are going to discuss, we are going to discuss how we can reduce the time

3
00:00:06,720 --> 00:00:08,630
and space complexity for this problem.

4
00:00:08,880 --> 00:00:14,430
So I already give you a hint that we can use the mathematical approach to reduce time and space complexity.

5
00:00:14,640 --> 00:00:19,620
And the problem and the solution that we are going to discuss today is very, very important because

6
00:00:19,620 --> 00:00:24,900
many times in ask this problem that can introduce time into space complexity for this.

7
00:00:25,020 --> 00:00:29,460
And if you haven't seen this video, then it will be really, really difficult for you to solve this

8
00:00:29,460 --> 00:00:30,390
problem in an interview.

9
00:00:30,660 --> 00:00:32,210
So let's discuss the problem.

10
00:00:33,000 --> 00:00:34,670
Let's discuss the solution basically.

11
00:00:35,130 --> 00:00:38,850
So we are provided with McCrossin Matrix.

12
00:00:42,470 --> 00:00:49,790
And how many steps we can take downward so we can take em minus one down steps.

13
00:00:51,740 --> 00:01:00,620
Right, and we can take and minus one right steps basically moving in the right direction, right to

14
00:01:00,620 --> 00:01:06,020
reach the end point, I'm repeating myself, AM metrics is given to us.

15
00:01:06,480 --> 00:01:09,860
We want to reach an endpoint so far reaching the end point.

16
00:01:10,040 --> 00:01:17,440
We are going to take minus one down step and and minus one right step simple right down step.

17
00:01:17,450 --> 00:01:20,090
I am representing my ID and right step.

18
00:01:20,090 --> 00:01:22,550
I am representing by our knowledge.

19
00:01:22,550 --> 00:01:24,530
Please hear my statement carefully.

20
00:01:24,770 --> 00:01:37,790
All the combination, all the permutations of M minus one down steps and and minus one right steps will

21
00:01:37,790 --> 00:01:38,960
reach the end point.

22
00:01:39,590 --> 00:01:46,970
I'm repeating myself all the combination, all the permutation of M minus one down step and N minus

23
00:01:46,970 --> 00:01:50,420
R right step will reach the end point.

24
00:01:50,440 --> 00:01:55,760
It does not matter when you take right step or when you take down step right.

25
00:01:55,940 --> 00:01:56,860
It doesn't matter.

26
00:01:56,870 --> 00:01:57,920
I'm repeating myself.

27
00:01:58,820 --> 00:02:04,790
It doesn't matter when you take right step or when you don't step, because ultimately the total number

28
00:02:04,790 --> 00:02:10,130
of steps downward will be minus one and the total number of steps right where it will be and minus one.

29
00:02:11,030 --> 00:02:12,800
So permutation is.

30
00:02:13,280 --> 00:02:14,630
So what will be the permutation?

31
00:02:17,300 --> 00:02:19,700
We need to take down steps.

32
00:02:20,910 --> 00:02:30,270
How many down steps and minus one times and we are going to take right steps, how many times that I

33
00:02:30,390 --> 00:02:32,640
step and the minus one times.

34
00:02:33,390 --> 00:02:40,710
So the formula for this is basically minus one plus and minus one.

35
00:02:42,110 --> 00:02:46,820
Factorial divided by M minus one factorial.

36
00:02:48,540 --> 00:02:51,580
And minus one Victorian, so this is the formula.

37
00:02:51,960 --> 00:02:54,450
This is the permutation formula.

38
00:02:54,840 --> 00:02:57,120
Now, let's simplify this formula a little bit.

39
00:02:58,510 --> 00:03:02,480
So if Multiemployer begins C minus and minus one, it will become minus two.

40
00:03:02,740 --> 00:03:13,750
So M plus and minus two factorial divided by M minus one factorial and minus one factorial.

41
00:03:15,070 --> 00:03:16,360
So this is our answer.

42
00:03:18,820 --> 00:03:22,680
This is the unique possible part, this is our answer, right?

43
00:03:22,980 --> 00:03:26,170
And now let's see how we can simplify this.

44
00:03:29,020 --> 00:03:36,220
So I'm writing the formula once again, so our answer is basically M plus and minus two factorial.

45
00:03:37,660 --> 00:03:43,390
Divided by and minus one factorial and and a minus one factorial.

46
00:03:44,170 --> 00:03:45,450
Now let's simplify this.

47
00:03:45,970 --> 00:03:47,990
So can I write it like this?

48
00:03:48,130 --> 00:03:53,620
One, two, three, four and so on and minus one.

49
00:03:54,850 --> 00:03:58,250
Then and these are all multiplication, right?

50
00:03:58,270 --> 00:03:59,710
These are all multiplications.

51
00:04:02,370 --> 00:04:12,900
Then it will be and plus one, then it will be an two and so on till and plus minus two.

52
00:04:14,570 --> 00:04:19,640
So I can write numerator like this and how can I write the denominator?

53
00:04:21,450 --> 00:04:23,370
So denominator will be.

54
00:04:24,720 --> 00:04:26,040
And minus on Vectorial.

55
00:04:27,090 --> 00:04:35,940
And N minus one Victorian, right, this is the denominator and if we can see so this and minus one

56
00:04:35,940 --> 00:04:38,190
factorial will cancel out this part.

57
00:04:41,380 --> 00:04:41,840
Right.

58
00:04:42,400 --> 00:04:50,110
This is basically tell this we have in mind this on Vectorial, so now what is our enumerator numerators

59
00:04:50,110 --> 00:04:50,440
and.

60
00:04:51,440 --> 00:04:52,430
And plus one.

61
00:04:54,000 --> 00:04:54,900
And to.

62
00:04:57,100 --> 00:05:08,680
And plus minus two, and what is our denominator, so our denominator is simply minus one factorial,

63
00:05:08,680 --> 00:05:16,720
which is nothing but one, two, three, four till M minus one.

64
00:05:17,760 --> 00:05:23,620
OK, so this is M minus one factorial starting from one till M minus one.

65
00:05:24,150 --> 00:05:25,320
So this is our answer.

66
00:05:26,310 --> 00:05:27,540
So how many?

67
00:05:28,650 --> 00:05:32,460
Values are present, how many values are present in the numerator so.

68
00:05:33,590 --> 00:05:37,340
These are basically M minus one Tumbes.

69
00:05:38,310 --> 00:05:44,580
In the numerator, we have M minus one times and in the denominator also we have minus Wyndham's.

70
00:05:46,490 --> 00:05:48,050
So this is our answer.

71
00:05:48,260 --> 00:05:51,330
We have the value of N and we also have the value of him.

72
00:05:51,650 --> 00:05:54,620
We just need to find out this value and that will be our answer.

73
00:05:55,760 --> 00:05:59,240
So let me write it clearly here and then I will write the code.

74
00:06:01,030 --> 00:06:03,790
So our answer is basically an.

75
00:06:04,860 --> 00:06:12,150
And plus one and plus two, and it will go on daily and plus and minus two.

76
00:06:13,650 --> 00:06:21,600
And in the denominator we have when we have two, we have three and it will go up to last and will be

77
00:06:21,670 --> 00:06:22,570
minus one.

78
00:06:22,920 --> 00:06:26,210
So this is our formula and now it's very simple gold.

79
00:06:26,430 --> 00:06:28,390
So let's just start writing the code.

80
00:06:28,710 --> 00:06:30,520
The code is going to be very, very simple.

81
00:06:31,200 --> 00:06:34,020
So first, let's comment about this code.

82
00:06:43,800 --> 00:06:45,100
OK, so what we need to do.

83
00:06:45,690 --> 00:06:53,350
Let's take a very long, long answer, very long, long, because we are multiplying so they may overflow.

84
00:06:53,670 --> 00:07:00,000
So to avoid stack overflow, so to avoid integer overflow, let's take long, long instead of integer.

85
00:07:01,050 --> 00:07:02,250
Now, what do we need?

86
00:07:02,250 --> 00:07:03,230
We need a for loop.

87
00:07:03,990 --> 00:07:07,510
And this for loop will start with.

88
00:07:07,510 --> 00:07:15,960
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

89
00:07:15,960 --> 00:07:16,560
from M..

90
00:07:17,100 --> 00:07:24,420
I will go till end plus M minus to find.

91
00:07:27,220 --> 00:07:40,250
I placeless and what we need to do, so our answer will be the correct answer, multiply and answer,

92
00:07:40,250 --> 00:07:49,480
you will be the correct answer divided by you can see here we are dividing by one, two, three delamination.

93
00:07:49,480 --> 00:07:56,740
So we will divide by a minus and plus one.

94
00:07:58,800 --> 00:08:07,440
So how I figured out this value, so it's very simple, so for and I want to divide by one, right.

95
00:08:07,860 --> 00:08:14,310
So the value of AI is basically and so forth, then I want to divide by one.

96
00:08:14,520 --> 00:08:21,240
So the put the value of equals and so and minus and plus one it will become one right.

97
00:08:21,420 --> 00:08:23,500
When the value of five will become and plus one.

98
00:08:23,790 --> 00:08:30,750
So when the value of AI is and plus one this value will become an minus and plus one.

99
00:08:31,170 --> 00:08:32,460
So this will become to.

100
00:08:33,730 --> 00:08:38,409
OK, so I'm doing like this for you, I will divide by three and so on.

101
00:08:39,760 --> 00:08:47,110
Separate whenever I become and plus and minus two and plus and minus two, what disvalue will become.

102
00:08:47,110 --> 00:08:52,270
So put the value of I and plus and minus two and this is minus N plus one.

103
00:08:52,900 --> 00:08:58,230
So minus in this, this is minus two degrees plus and minus one.

104
00:08:58,630 --> 00:09:00,760
So this will become M minus denominate.

105
00:09:00,760 --> 00:09:01,130
Right.

106
00:09:01,840 --> 00:09:03,850
So this logic is correct.

107
00:09:06,860 --> 00:09:10,630
And now what we need to do, simple, we just need to return our answer.

108
00:09:13,180 --> 00:09:21,730
We simply need to return our answer, but as you can see here, the return type is integer and the return

109
00:09:21,730 --> 00:09:24,700
type of answer variable is basically longlong.

110
00:09:24,700 --> 00:09:26,950
So let's typecast and then we will return.

111
00:09:31,710 --> 00:09:35,630
So now let's try to submit our code and let's see whether it will work or not.

112
00:09:39,170 --> 00:09:44,960
Yeah, so basically our solution is working and now let us try to find out the time and the space complexity

113
00:09:44,960 --> 00:09:49,940
for the solution, so as we can see, we are not using any extra space.

114
00:09:50,240 --> 00:09:54,980
So the space complexity is basically big off when and what is the time complexity.

115
00:09:55,130 --> 00:09:56,720
So we are just iterating.

116
00:09:56,810 --> 00:10:00,220
And how many times are there M minus one comes out there.

117
00:10:00,410 --> 00:10:04,160
So time, complexity, we can say big off and minus and all we can save time.

118
00:10:04,160 --> 00:10:06,200
Complexity is basically big of M.

119
00:10:07,410 --> 00:10:07,840
Right.

120
00:10:08,460 --> 00:10:15,150
So what we can do, so suppose if the value of em is much, much, much, much good then and then instead

121
00:10:15,150 --> 00:10:19,230
of this formula so we can sell and minus one factorial, if you remember.

122
00:10:19,380 --> 00:10:23,670
So instead of cancelling and minus unfactual, I will cancel M minus on Vectorial.

123
00:10:24,420 --> 00:10:29,140
So here you can write one check, you can write if health condition.

124
00:10:29,430 --> 00:10:34,080
So if the value of M is good then nd then this solution.

125
00:10:34,890 --> 00:10:36,090
Sorry if the value of.

126
00:10:37,680 --> 00:10:38,210
So I decided.

127
00:10:38,400 --> 00:10:42,490
So if the value of N is guerdon M then the solution is correct.

128
00:10:42,690 --> 00:10:47,140
Otherwise you need to cancel M minus and then you can modify this code.

129
00:10:47,250 --> 00:10:54,900
So basically instead of writing big arfin, what I will do, I will write big off minimum of M comma

130
00:10:54,960 --> 00:10:55,200
and.

131
00:10:59,130 --> 00:11:04,190
I'm repeating myself so far, this code, the code that I have written, the time complexities big off

132
00:11:04,200 --> 00:11:07,730
em, but what is the improvisation?

133
00:11:07,740 --> 00:11:12,510
What is the improvement that I am suggesting is so it can happen and is much, much lower than.

134
00:11:12,510 --> 00:11:18,270
And then in that case, if you remember in bulk and reading the formula I was canceling and minus one

135
00:11:18,270 --> 00:11:18,800
factorial.

136
00:11:18,990 --> 00:11:21,990
So if this is the case, then you will cancel and minus one factorial.

137
00:11:22,120 --> 00:11:25,460
Similarly, your formula will change and your code will also change.

138
00:11:25,800 --> 00:11:31,350
So that's why I am writing that after improving the school, our time complexity will become big of

139
00:11:31,350 --> 00:11:35,730
a minimum of M and then so you can see our time complexities linear.

140
00:11:37,040 --> 00:11:43,220
Our time complexity is linear and space complexity is basically constant, so our algorithm has become

141
00:11:43,520 --> 00:11:44,810
very, very optimized.

142
00:11:45,230 --> 00:11:50,500
So this court is really, really optimized as compared to our previous code.

143
00:11:50,810 --> 00:11:56,720
And I suggest you watching this video before you go for an interview, because many times you will be

144
00:11:56,720 --> 00:11:57,980
able to give this approach.

145
00:11:57,980 --> 00:12:04,280
But we will say give me a better approach and this is the better approach, a mathematical approach.

146
00:12:05,150 --> 00:12:06,620
So this is it from this video.

147
00:12:06,620 --> 00:12:08,660
Guys, I will see you in the next one.

148
00:12:08,780 --> 00:12:09,350
Thank you.