1
00:00:01,310 --> 00:00:02,009
Hi, everyone.

2
00:00:02,029 --> 00:00:07,910
So today in this video, we are going to solve this question, find the square root of a number X,

3
00:00:08,210 --> 00:00:10,640
so X will be basically an integer.

4
00:00:10,670 --> 00:00:16,219
OK, so X is basically integer and we have to implement this function square root.

5
00:00:16,470 --> 00:00:25,250
OK, so basically our input is basically Ainger and our output will be we have to find the square root

6
00:00:25,250 --> 00:00:26,390
of that integer.

7
00:00:26,450 --> 00:00:29,370
OK, so we only have to find the integer part.

8
00:00:30,290 --> 00:00:32,820
OK, so what do I mean by integer part let's say.

9
00:00:32,840 --> 00:00:37,220
So if this is our input then the square root of four is basically two.

10
00:00:38,570 --> 00:00:41,170
Square root of four is basically too narrow.

11
00:00:41,170 --> 00:00:44,570
To consider this example, I have to find the square root of it.

12
00:00:44,820 --> 00:00:49,700
OK, so the square root of it will be basically two point eight point something.

13
00:00:50,030 --> 00:00:53,280
OK, and but we have to find only the integer part.

14
00:00:53,570 --> 00:00:56,570
So what we can do, we can truncate the fractional part.

15
00:00:56,810 --> 00:00:59,120
So our output will basically be two.

16
00:01:00,250 --> 00:01:06,730
OK, so Ford, we have to find the square root of 10, so scared of 10 will be three point something,

17
00:01:06,730 --> 00:01:07,180
something.

18
00:01:07,390 --> 00:01:10,770
OK, but we only have to find the integer part.

19
00:01:11,050 --> 00:01:15,960
So what we can do, we can truncate the friction part so our output will be three.

20
00:01:16,450 --> 00:01:16,780
OK.

21
00:01:17,080 --> 00:01:19,040
So I hope you understood this question.

22
00:01:19,060 --> 00:01:25,180
So this question is basically a little question and now let us see how we can solve this question.

23
00:01:25,300 --> 00:01:28,060
OK, so let us consider the first approach.

24
00:01:28,060 --> 00:01:29,630
So naive approach.

25
00:01:29,650 --> 00:01:30,850
So this is very simple.

26
00:01:31,300 --> 00:01:34,330
OK, so what we can do, let us consider an example.

27
00:01:34,340 --> 00:01:38,050
So suppose our input is basically, let's say 50.

28
00:01:38,870 --> 00:01:41,540
OK, we have to find the square root of 50.

29
00:01:41,710 --> 00:01:44,960
So what we will do so we will try all the numbers.

30
00:01:45,130 --> 00:01:47,860
So first of all, what I will do, I will find the square root.

31
00:01:47,860 --> 00:01:49,210
I will find the square of one.

32
00:01:49,210 --> 00:01:49,900
I will take one.

33
00:01:50,350 --> 00:01:52,440
So one square is less than 50.

34
00:01:53,260 --> 00:01:54,850
So what I will do, I will take two.

35
00:01:55,120 --> 00:01:58,250
So two square is again less than 50, then take three.

36
00:01:58,570 --> 00:02:01,780
So three square is less than 50, then take four.

37
00:02:01,960 --> 00:02:04,880
So four square is less than 50, then take five.

38
00:02:05,200 --> 00:02:09,370
So five square is less than 50, then take six.

39
00:02:09,520 --> 00:02:12,940
So six square is less than 50, then take seven.

40
00:02:13,150 --> 00:02:15,410
So seven square is less than 50.

41
00:02:15,580 --> 00:02:19,050
Then take it so each square will be greater than 50.

42
00:02:19,360 --> 00:02:22,900
OK, so at this moment, what I will do, I will stop.

43
00:02:24,290 --> 00:02:25,770
And what will be my answer?

44
00:02:25,790 --> 00:02:27,830
So my answer will basically be seven.

45
00:02:28,010 --> 00:02:30,720
OK, so my output will be seven.

46
00:02:30,740 --> 00:02:33,500
OK, so scared of 50 will give me seven.

47
00:02:33,960 --> 00:02:36,080
OK, so this is very simple approach.

48
00:02:36,320 --> 00:02:43,190
So what we will do, we will start from one and we will keep going on till the let's say this is X,

49
00:02:43,190 --> 00:02:53,070
so tell X squared is less than 50 and when the X squared becomes larger than 50, we will stop, OK.

50
00:02:53,270 --> 00:02:57,920
And so in this example, I will stop at eight and my answer will be seven.

51
00:02:58,140 --> 00:03:00,710
OK, so this will be very simple approach.

52
00:03:00,740 --> 00:03:04,040
Now what is the time and the space complexity for using this approach?

53
00:03:04,730 --> 00:03:10,220
So first of all, let's discuss the space complexity so we are not using any extra space.

54
00:03:10,460 --> 00:03:12,890
So the space complexity will be our draughtsman.

55
00:03:13,160 --> 00:03:15,870
And now let's discuss the time complexity.

56
00:03:16,160 --> 00:03:20,120
So 450, the maximum that I will go will be eight.

57
00:03:20,630 --> 00:03:24,170
OK, so basically the time complexity will be squared off.

58
00:03:24,170 --> 00:03:25,010
The given number.

59
00:03:25,990 --> 00:03:34,090
OK, so it was a given number was and then the time complexities squared off and OK, so this is the

60
00:03:34,090 --> 00:03:34,740
new approach.

61
00:03:35,140 --> 00:03:40,420
Now, the second approach for solving this question is with the help of binary search.

62
00:03:41,200 --> 00:03:44,990
OK, so how we can use the binary search for solving this question.

63
00:03:45,430 --> 00:03:46,840
So this is very simple.

64
00:03:47,860 --> 00:03:53,470
So what we will do so suppose I want to find the square root of Ben.

65
00:03:53,560 --> 00:03:55,540
OK, let us consider a small example.

66
00:03:55,930 --> 00:03:57,760
So I want to find the square root of Ben.

67
00:03:58,690 --> 00:04:04,900
So first of all, for Binish, such our area should be sorted, but we do not have area here, but we

68
00:04:04,900 --> 00:04:05,560
have numbers.

69
00:04:05,680 --> 00:04:06,690
So what are the numbers?

70
00:04:07,090 --> 00:04:10,980
So we have one, two, three and so on, Dilton.

71
00:04:11,050 --> 00:04:13,680
OK, so I'm picking 10 as an example.

72
00:04:13,990 --> 00:04:16,589
So I have numbers from one to 10.

73
00:04:16,899 --> 00:04:18,860
OK, so let me read the numbers.

74
00:04:19,750 --> 00:04:25,750
So this is one, two, three, four, five, six, seven, eight, nine and 10.

75
00:04:25,760 --> 00:04:28,630
And my goal is to find the square root of ten.

76
00:04:29,170 --> 00:04:30,930
So I will use the binary search approach.

77
00:04:31,570 --> 00:04:32,830
This will be my start.

78
00:04:33,730 --> 00:04:35,110
This will be my end.

79
00:04:35,310 --> 00:04:37,030
OK, I will find out.

80
00:04:37,150 --> 00:04:39,780
It will be start plus end by two.

81
00:04:39,790 --> 00:04:46,800
So basically it will be ten plus one by two, so 11 by two which will basically be five.

82
00:04:46,840 --> 00:04:50,250
OK, it will be 5.5 but integer one integer.

83
00:04:50,830 --> 00:04:54,370
So this is integer divided where integer.

84
00:04:54,370 --> 00:04:58,510
So the output will be integer only so the output will basically be five.

85
00:04:58,730 --> 00:05:00,400
OK, so five.

86
00:05:01,330 --> 00:05:02,800
So this is my mid.

87
00:05:03,810 --> 00:05:11,220
Now, what I will do, I will compare made squid, OK, so I will find made squid.

88
00:05:11,220 --> 00:05:12,960
So this is made in tumed.

89
00:05:14,020 --> 00:05:20,980
And then I will compare with the given number, which is 10, so square is basically greater than 10.

90
00:05:21,070 --> 00:05:24,770
OK, so five square, which is 25 is good, then 10.

91
00:05:24,790 --> 00:05:27,010
So what I will do, I will update my end.

92
00:05:27,250 --> 00:05:27,910
OK, so.

93
00:05:27,910 --> 00:05:30,610
And will become made minus one.

94
00:05:30,640 --> 00:05:33,430
OK, so case one if.

95
00:05:36,140 --> 00:05:39,060
Made square is greater than the government.

96
00:05:39,080 --> 00:05:43,670
But what I will do, I will update my SO and will become minus one.

97
00:05:43,700 --> 00:05:48,040
OK, so remove and from here, put and here.

98
00:05:48,170 --> 00:05:49,610
So this is my new end.

99
00:05:49,690 --> 00:05:52,130
OK, so this is my new end.

100
00:05:53,200 --> 00:05:54,520
Now, again, I will find out.

101
00:05:55,330 --> 00:05:57,040
So in this case, what the.

102
00:05:57,560 --> 00:06:02,490
So this will be one plus four by two, which is five by two.

103
00:06:02,620 --> 00:06:03,670
So this will be two.

104
00:06:04,180 --> 00:06:06,580
OK, so this is my Numata.

105
00:06:07,720 --> 00:06:08,690
This is my moment.

106
00:06:08,920 --> 00:06:10,300
Now find out Metzker.

107
00:06:10,570 --> 00:06:17,000
So midscale means to square which is four and four is basically less than ten.

108
00:06:18,070 --> 00:06:22,930
OK so what I'm going to do I will start equals mid plus one.

109
00:06:23,260 --> 00:06:24,870
Now this is my second case.

110
00:06:25,300 --> 00:06:26,110
So if.

111
00:06:27,630 --> 00:06:35,580
The middle square is less than the government, but what I will do, I will start equals method plus

112
00:06:35,580 --> 00:06:35,820
one.

113
00:06:36,850 --> 00:06:43,360
OK, so remove start from here and start will come here.

114
00:06:44,450 --> 00:06:49,340
OK, so this is a start and this is and now let us again find out.

115
00:06:50,570 --> 00:06:53,470
OK, let us again try to find out mid.

116
00:06:55,130 --> 00:06:59,160
So there's basically three plus four by two.

117
00:06:59,330 --> 00:07:05,870
So seven vital and seven vital buses, basically three again, find out mate square.

118
00:07:06,500 --> 00:07:09,290
So square basically means three square, which is nine.

119
00:07:09,440 --> 00:07:11,540
So nine is less than ten.

120
00:07:11,600 --> 00:07:15,020
OK, so this case, second case, this is the second case.

121
00:07:15,260 --> 00:07:18,100
So what I'm going to do is start equals plus one.

122
00:07:18,740 --> 00:07:23,470
OK, so remove and this will be my starter.

123
00:07:24,230 --> 00:07:28,550
OK, now one thing, whenever you are doing start equals one plus one.

124
00:07:30,570 --> 00:07:34,050
First, what we have to do, we have to store our temporary answer.

125
00:07:34,080 --> 00:07:36,450
So answer will be basically made.

126
00:07:37,470 --> 00:07:42,000
First is truly a temporary answer and then try to find out the answer on the right hand side.

127
00:07:42,540 --> 00:07:48,750
OK, so what I'm going to do here is so first of all, I will store three here.

128
00:07:48,820 --> 00:07:50,220
OK, so there will be three.

129
00:07:52,370 --> 00:07:59,930
OK, so answer is three, and then this is my start and this is my end now, Melville basically four

130
00:07:59,930 --> 00:08:06,470
plus four by two, which is basically four only and then four square is good.

131
00:08:06,470 --> 00:08:12,860
Then basically 10, 16 is good, then 10, then I will do underclassman minus one so and will come here

132
00:08:13,760 --> 00:08:16,130
and start become good then.

133
00:08:16,130 --> 00:08:22,220
And so I will stop, my loop will stop and my answer will be basically three.

134
00:08:23,430 --> 00:08:25,290
My answer will be in basically three.

135
00:08:26,230 --> 00:08:29,860
OK, so I have two conditions and rather two condition.

136
00:08:30,970 --> 00:08:31,930
So if.

137
00:08:33,200 --> 00:08:37,549
Red Square is good then and.

138
00:08:38,740 --> 00:08:40,870
Then obviously, it cannot be our answer.

139
00:08:41,059 --> 00:08:48,400
OK, so this is my case one, if my square is a garden and then it cannot be our answer.

140
00:08:48,820 --> 00:08:52,210
OK, so I will simply do made minus one.

141
00:08:53,410 --> 00:08:57,040
I have to go on the left hand side and the second case.

142
00:08:58,130 --> 00:08:58,640
If.

143
00:09:00,240 --> 00:09:04,140
Main square is less than then it can be our answer.

144
00:09:04,380 --> 00:09:09,630
OK, to for 10 buscaglia less than 10 sorto can be our answer.

145
00:09:10,260 --> 00:09:13,100
One square is less than 10, so one can be our answer.

146
00:09:13,560 --> 00:09:16,560
Three square is less than 10, so three can be able to answer.

147
00:09:16,860 --> 00:09:18,540
Four Square is guerdon 10.

148
00:09:18,540 --> 00:09:20,640
So four cannot be our answer.

149
00:09:21,180 --> 00:09:24,100
OK, so that's why Enfamil Square is less than.

150
00:09:24,110 --> 00:09:26,310
And then we have a potential answer.

151
00:09:26,700 --> 00:09:30,480
So I will store that potential answer in a variable.

152
00:09:31,570 --> 00:09:38,260
And the name of the variable is basically answer, and then what I'm doing here is so I have to update,

153
00:09:38,450 --> 00:09:43,060
I have to find a good answer, so I will go in the right hand side.

154
00:09:43,490 --> 00:09:48,370
OK, so suppose I am telling you that one square can be our answer.

155
00:09:48,400 --> 00:09:52,930
So what I will do, I will store one and then I will move ahead.

156
00:09:53,440 --> 00:09:55,190
So again, two can be our answer.

157
00:09:55,210 --> 00:09:57,840
So I will update and I will move ahead.

158
00:09:58,180 --> 00:09:59,540
So three can be our answer.

159
00:09:59,560 --> 00:10:01,740
So I will update and move ahead.

160
00:10:02,050 --> 00:10:03,940
So Foursquare is good then 10.

161
00:10:04,690 --> 00:10:08,770
So that means this condition will be executed and our loop will stop.

162
00:10:08,800 --> 00:10:14,070
OK, so this was basically for understanding purpose, remove it from here.

163
00:10:14,350 --> 00:10:18,310
So I just want to tell you that these are the two conditions, OK?

164
00:10:18,310 --> 00:10:20,070
And these are very simple conditions.

165
00:10:20,500 --> 00:10:27,520
So what you have to remember, if Metzker is good then the number and then cannot be our answer.

166
00:10:27,550 --> 00:10:30,250
So I'm simply doing and equals no minus one.

167
00:10:30,550 --> 00:10:36,500
But if this is the condition then we have a potential answer and we are storing that potential also

168
00:10:36,580 --> 00:10:41,530
in a variable answer and then we are trying to find a good answer on the right hand side.

169
00:10:42,400 --> 00:10:46,750
OK, and finally our loop will stop and we will return the answer.

170
00:10:47,890 --> 00:10:53,410
OK, so what will be the time complexity, since we are using Binay such short term complexities?

171
00:10:53,410 --> 00:10:56,350
Logan and the space complexities are the rough one.

172
00:10:56,970 --> 00:11:03,550
OK, so here we can see in this question how we are able to use binary search.

173
00:11:03,760 --> 00:11:09,670
So it is not necessary that we will be given a vector and that vector will be sorted, then only you

174
00:11:09,670 --> 00:11:11,140
will use binary search.

175
00:11:11,320 --> 00:11:12,450
It is not necessary.

176
00:11:12,450 --> 00:11:13,720
It doesn't work like that.

177
00:11:13,790 --> 00:11:16,960
OK, so bindis which can be used in question like this also.

178
00:11:17,260 --> 00:11:23,050
OK, so you have to figure out yourself whether I can use my new search or how so it can be used in

179
00:11:23,050 --> 00:11:23,680
this question.

180
00:11:23,950 --> 00:11:26,550
OK, now let us write the code.

181
00:11:27,190 --> 00:11:32,640
So I am not writing the script, I am not writing the knife called the brute force code.

182
00:11:32,650 --> 00:11:33,690
You can write it to yourself.

183
00:11:33,730 --> 00:11:34,510
It is very easy.

184
00:11:34,790 --> 00:11:40,570
You start from one and you go to square root of an OK, so let us implement the Binay such good.

185
00:11:41,230 --> 00:11:41,380
OK.

186
00:11:41,470 --> 00:11:43,630
So first let us handle some cases.

187
00:11:43,630 --> 00:11:45,580
So are zero.

188
00:11:45,760 --> 00:11:47,190
OK, X is our number.

189
00:11:47,200 --> 00:11:51,490
Then the square root of X squared of zero is basically zero only.

190
00:11:52,120 --> 00:11:56,710
OK, now for implementing the minus search we need to pointer start engine.

191
00:11:56,710 --> 00:11:57,970
So start this basically.

192
00:11:57,970 --> 00:11:58,990
Let's start from one.

193
00:11:59,080 --> 00:11:59,440
OK.

194
00:12:00,450 --> 00:12:05,540
Let's start from one and our end will be basically the given number.

195
00:12:05,730 --> 00:12:06,080
OK.

196
00:12:07,480 --> 00:12:11,470
So we'll start as less tonight, of course, to end, we will find out.

197
00:12:12,250 --> 00:12:17,040
OK, so let's find out which is nothing but start listening to.

198
00:12:19,260 --> 00:12:20,950
And now that is confirmed.

199
00:12:21,720 --> 00:12:23,100
So if Mitt.

200
00:12:24,790 --> 00:12:29,600
And entombment, is it close to the given number, then we can simply return?

201
00:12:30,200 --> 00:12:30,620
OK.

202
00:12:32,940 --> 00:12:34,200
Now, in the elusive.

203
00:12:36,060 --> 00:12:37,500
So if Myrt.

204
00:12:38,660 --> 00:12:45,800
Square is less than X then what we have to do, so we have to find our arms on the right hand side,

205
00:12:45,800 --> 00:12:48,730
so start equals melt plus one.

206
00:12:48,740 --> 00:12:54,310
But before doing this, what they have to do, it will store this as our answer as ever.

207
00:12:54,320 --> 00:12:55,900
It can be our potential answer.

208
00:12:56,120 --> 00:12:58,430
Senators also take a variable answer.

209
00:12:59,640 --> 00:13:03,450
OK, so first we will store and then we will update.

210
00:13:04,690 --> 00:13:09,400
And similarly, in the early part, we will simply do and equal treatment minus one.

211
00:13:11,280 --> 00:13:12,930
OK, and finally.

212
00:13:15,210 --> 00:13:18,200
What we can do so we can return our answer.

213
00:13:19,620 --> 00:13:22,680
OK, so let's Rancourt and then we will submit.

214
00:13:24,370 --> 00:13:27,900
And then let's see if we can optimize our code a little bit more.

215
00:13:30,300 --> 00:13:31,610
OK, now that summit.

216
00:13:37,210 --> 00:13:43,600
OK, so we are getting married, OK, and see integer overflow.

217
00:13:45,650 --> 00:13:48,380
Now, let's see, we are getting better at this line.

218
00:13:48,410 --> 00:13:54,740
OK, so multiply it looks so why we are getting an edit, let us try to understand, OK?

219
00:13:57,650 --> 00:14:01,670
So what we are doing here is so suppose made.

220
00:14:03,050 --> 00:14:09,090
Is integer or Kimbal will be, it is obviously an integer, and let's suppose it's a very large integer.

221
00:14:09,160 --> 00:14:12,070
OK, so it's a very large integer.

222
00:14:12,290 --> 00:14:19,970
And what we are doing here is basically we are multiplying two large integers, OK, so large integer

223
00:14:20,480 --> 00:14:25,600
squared, OK, and this large integer square, what will happen.

224
00:14:25,610 --> 00:14:31,190
So there's a possibility that this large integer square cannot be stored in an integer variable.

225
00:14:31,490 --> 00:14:34,410
OK, so as we know, there is a limit.

226
00:14:34,430 --> 00:14:36,620
So what is the limit for integer.

227
00:14:38,060 --> 00:14:40,850
So it is basically two to the power to one minus one.

228
00:14:40,880 --> 00:14:44,810
OK, so this is the biggest number that we can store inside an integer.

229
00:14:44,940 --> 00:14:47,960
OK, so approximately this is 10 to the power nine.

230
00:14:48,590 --> 00:14:54,050
OK, now suppose this large integer is, let's say 10 to the power six and what we are doing.

231
00:14:54,380 --> 00:14:56,490
So this will become 10 to the power 12.

232
00:14:56,750 --> 00:14:59,190
This magenta will become 10 to the power 12.

233
00:14:59,510 --> 00:15:01,700
And this is a very big integer.

234
00:15:01,910 --> 00:15:05,660
And obviously this cannot be stored in an integer variable.

235
00:15:06,260 --> 00:15:12,710
OK, so the one way to handle this problem is basically what you can do is take everything longlong.

236
00:15:14,210 --> 00:15:19,320
OK, use this today, type Longlong, so the range of this is basically ten to the power 18.

237
00:15:19,800 --> 00:15:22,010
OK, so double double of this one.

238
00:15:22,340 --> 00:15:26,100
So this is basically standard operating so long, long will work fine.

239
00:15:26,390 --> 00:15:33,440
Now the second way to solve this problem is what we are doing here is we are writing to Mel and we are

240
00:15:33,440 --> 00:15:36,150
doing multiplication and then we are comparing.

241
00:15:36,950 --> 00:15:39,740
So what we can do, so can we write it like this.

242
00:15:40,520 --> 00:15:44,380
Mid equals equals X divided by mid.

243
00:15:45,600 --> 00:15:51,790
OK, if we will write code like this, then we will not get in digital flight.

244
00:15:52,440 --> 00:15:57,690
OK, because here we are dividing so our number will become smaller.

245
00:15:58,050 --> 00:16:04,000
OK, our number will become smaller and we will not get integer overflow or you can say random error.

246
00:16:04,020 --> 00:16:06,890
So here we are getting overflow see overflow at it.

247
00:16:07,860 --> 00:16:09,390
So if we will write it like this.

248
00:16:11,140 --> 00:16:12,100
This will work fine.

249
00:16:12,130 --> 00:16:14,590
OK, so instead of multiplication.

250
00:16:16,320 --> 00:16:18,860
They will write X divided by mid.

251
00:16:19,990 --> 00:16:21,190
And same for this one.

252
00:16:23,540 --> 00:16:25,190
X divide by mid.

253
00:16:25,590 --> 00:16:29,620
OK, now let's summit it, so hopefully they should work fine.

254
00:16:34,500 --> 00:16:36,660
So, again, we are getting all flooded.

255
00:16:37,860 --> 00:16:40,270
We are getting ready for this line now.

256
00:16:40,350 --> 00:16:47,640
We all know the better way to write this is basically start plus and minus, start by two.

257
00:16:50,610 --> 00:16:52,110
OK, now let's admit.

258
00:16:55,660 --> 00:16:58,060
OK, so now our court is looking for an.

259
00:16:59,710 --> 00:17:02,930
So many times I've already explained this thing.

260
00:17:03,280 --> 00:17:08,560
So START is a big number and is a big number, and the other day you are adding two numbers and then

261
00:17:08,560 --> 00:17:09,470
you are dividing by two.

262
00:17:09,700 --> 00:17:15,160
So when you are adding two very large integer, there is a possibility that it will it cannot be contained

263
00:17:15,160 --> 00:17:16,740
inside an integer variable.

264
00:17:17,020 --> 00:17:23,680
So that's why this is a good way to write and minus to start first subtract that number becomes smaller

265
00:17:23,680 --> 00:17:24,520
and then you can add.

266
00:17:24,800 --> 00:17:28,220
OK, ok, so what is the time and the space complexity.

267
00:17:28,240 --> 00:17:31,720
So we have already discussed since we are using binary search.

268
00:17:32,050 --> 00:17:35,830
So time complexities, Logan and space complexities or the rough one.

269
00:17:36,040 --> 00:17:40,270
OK, so if you have any doubt in this question you can ask me.

270
00:17:40,280 --> 00:17:41,110
OK, thank you.

