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.