Hi, everyone.
So today in this video, we are going to solve this question, find the square root of a number X,
so X will be basically an integer.
OK, so X is basically integer and we have to implement this function square root.
OK, so basically our input is basically Ainger and our output will be we have to find the square root
of that integer.
OK, so we only have to find the integer part.
OK, so what do I mean by integer part let's say.
So if this is our input then the square root of four is basically two.
Square root of four is basically too narrow.
To consider this example, I have to find the square root of it.
OK, so the square root of it will be basically two point eight point something.
OK, and but we have to find only the integer part.
So what we can do, we can truncate the fractional part.
So our output will basically be two.
OK, so Ford, we have to find the square root of 10, so scared of 10 will be three point something,
something.
OK, but we only have to find the integer part.
So what we can do, we can truncate the friction part so our output will be three.
OK.
So I hope you understood this question.
So this question is basically a little question and now let us see how we can solve this question.
OK, so let us consider the first approach.
So naive approach.
So this is very simple.
OK, so what we can do, let us consider an example.
So suppose our input is basically, let's say 50.
OK, we have to find the square root of 50.
So what we will do so we will try all the numbers.
So first of all, what I will do, I will find the square root.
I will find the square of one.
I will take one.
So one square is less than 50.
So what I will do, I will take two.
So two square is again less than 50, then take three.
So three square is less than 50, then take four.
So four square is less than 50, then take five.
So five square is less than 50, then take six.
So six square is less than 50, then take seven.
So seven square is less than 50.
Then take it so each square will be greater than 50.
OK, so at this moment, what I will do, I will stop.
And what will be my answer?
So my answer will basically be seven.
OK, so my output will be seven.
OK, so scared of 50 will give me seven.
OK, so this is very simple approach.
So what we will do, we will start from one and we will keep going on till the let's say this is X,
so tell X squared is less than 50 and when the X squared becomes larger than 50, we will stop, OK.
And so in this example, I will stop at eight and my answer will be seven.
OK, so this will be very simple approach.
Now what is the time and the space complexity for using this approach?
So first of all, let's discuss the space complexity so we are not using any extra space.
So the space complexity will be our draughtsman.
And now let's discuss the time complexity.
So 450, the maximum that I will go will be eight.
OK, so basically the time complexity will be squared off.
The given number.
OK, so it was a given number was and then the time complexities squared off and OK, so this is the
new approach.
Now, the second approach for solving this question is with the help of binary search.
OK, so how we can use the binary search for solving this question.
So this is very simple.
So what we will do so suppose I want to find the square root of Ben.
OK, let us consider a small example.
So I want to find the square root of Ben.
So first of all, for Binish, such our area should be sorted, but we do not have area here, but we
have numbers.
So what are the numbers?
So we have one, two, three and so on, Dilton.
OK, so I'm picking 10 as an example.
So I have numbers from one to 10.
OK, so let me read the numbers.
So this is one, two, three, four, five, six, seven, eight, nine and 10.
And my goal is to find the square root of ten.
So I will use the binary search approach.
This will be my start.
This will be my end.
OK, I will find out.
It will be start plus end by two.
So basically it will be ten plus one by two, so 11 by two which will basically be five.
OK, it will be 5.5 but integer one integer.
So this is integer divided where integer.
So the output will be integer only so the output will basically be five.
OK, so five.
So this is my mid.
Now, what I will do, I will compare made squid, OK, so I will find made squid.
So this is made in tumed.
And then I will compare with the given number, which is 10, so square is basically greater than 10.
OK, so five square, which is 25 is good, then 10.
So what I will do, I will update my end.
OK, so.
And will become made minus one.
OK, so case one if.
Made square is greater than the government.
But what I will do, I will update my SO and will become minus one.
OK, so remove and from here, put and here.
So this is my new end.
OK, so this is my new end.
Now, again, I will find out.
So in this case, what the.
So this will be one plus four by two, which is five by two.
So this will be two.
OK, so this is my Numata.
This is my moment.
Now find out Metzker.
So midscale means to square which is four and four is basically less than ten.
OK so what I'm going to do I will start equals mid plus one.
Now this is my second case.
So if.
The middle square is less than the government, but what I will do, I will start equals method plus
one.
OK, so remove start from here and start will come here.
OK, so this is a start and this is and now let us again find out.
OK, let us again try to find out mid.
So there's basically three plus four by two.
So seven vital and seven vital buses, basically three again, find out mate square.
So square basically means three square, which is nine.
So nine is less than ten.
OK, so this case, second case, this is the second case.
So what I'm going to do is start equals plus one.
OK, so remove and this will be my starter.
OK, now one thing, whenever you are doing start equals one plus one.
First, what we have to do, we have to store our temporary answer.
So answer will be basically made.
First is truly a temporary answer and then try to find out the answer on the right hand side.
OK, so what I'm going to do here is so first of all, I will store three here.
OK, so there will be three.
OK, so answer is three, and then this is my start and this is my end now, Melville basically four
plus four by two, which is basically four only and then four square is good.
Then basically 10, 16 is good, then 10, then I will do underclassman minus one so and will come here
and start become good then.
And so I will stop, my loop will stop and my answer will be basically three.
My answer will be in basically three.
OK, so I have two conditions and rather two condition.
So if.
Red Square is good then and.
Then obviously, it cannot be our answer.
OK, so this is my case one, if my square is a garden and then it cannot be our answer.
OK, so I will simply do made minus one.
I have to go on the left hand side and the second case.
If.
Main square is less than then it can be our answer.
OK, to for 10 buscaglia less than 10 sorto can be our answer.
One square is less than 10, so one can be our answer.
Three square is less than 10, so three can be able to answer.
Four Square is guerdon 10.
So four cannot be our answer.
OK, so that's why Enfamil Square is less than.
And then we have a potential answer.
So I will store that potential answer in a variable.
And the name of the variable is basically answer, and then what I'm doing here is so I have to update,
I have to find a good answer, so I will go in the right hand side.
OK, so suppose I am telling you that one square can be our answer.
So what I will do, I will store one and then I will move ahead.
So again, two can be our answer.
So I will update and I will move ahead.
So three can be our answer.
So I will update and move ahead.
So Foursquare is good then 10.
So that means this condition will be executed and our loop will stop.
OK, so this was basically for understanding purpose, remove it from here.
So I just want to tell you that these are the two conditions, OK?
And these are very simple conditions.
So what you have to remember, if Metzker is good then the number and then cannot be our answer.
So I'm simply doing and equals no minus one.
But if this is the condition then we have a potential answer and we are storing that potential also
in a variable answer and then we are trying to find a good answer on the right hand side.
OK, and finally our loop will stop and we will return the answer.
OK, so what will be the time complexity, since we are using Binay such short term complexities?
Logan and the space complexities are the rough one.
OK, so here we can see in this question how we are able to use binary search.
So it is not necessary that we will be given a vector and that vector will be sorted, then only you
will use binary search.
It is not necessary.
It doesn't work like that.
OK, so bindis which can be used in question like this also.
OK, so you have to figure out yourself whether I can use my new search or how so it can be used in
this question.
OK, now let us write the code.
So I am not writing the script, I am not writing the knife called the brute force code.
You can write it to yourself.
It is very easy.
You start from one and you go to square root of an OK, so let us implement the Binay such good.
OK.
So first let us handle some cases.
So are zero.
OK, X is our number.
Then the square root of X squared of zero is basically zero only.
OK, now for implementing the minus search we need to pointer start engine.
So start this basically.
Let's start from one.
OK.
Let's start from one and our end will be basically the given number.
OK.
So we'll start as less tonight, of course, to end, we will find out.
OK, so let's find out which is nothing but start listening to.
And now that is confirmed.
So if Mitt.
And entombment, is it close to the given number, then we can simply return?
OK.
Now, in the elusive.
So if Myrt.
Square is less than X then what we have to do, so we have to find our arms on the right hand side,
so start equals melt plus one.
But before doing this, what they have to do, it will store this as our answer as ever.
It can be our potential answer.
Senators also take a variable answer.
OK, so first we will store and then we will update.
And similarly, in the early part, we will simply do and equal treatment minus one.
OK, and finally.
What we can do so we can return our answer.
OK, so let's Rancourt and then we will submit.
And then let's see if we can optimize our code a little bit more.
OK, now that summit.
OK, so we are getting married, OK, and see integer overflow.
Now, let's see, we are getting better at this line.
OK, so multiply it looks so why we are getting an edit, let us try to understand, OK?
So what we are doing here is so suppose made.
Is integer or Kimbal will be, it is obviously an integer, and let's suppose it's a very large integer.
OK, so it's a very large integer.
And what we are doing here is basically we are multiplying two large integers, OK, so large integer
squared, OK, and this large integer square, what will happen.
So there's a possibility that this large integer square cannot be stored in an integer variable.
OK, so as we know, there is a limit.
So what is the limit for integer.
So it is basically two to the power to one minus one.
OK, so this is the biggest number that we can store inside an integer.
OK, so approximately this is 10 to the power nine.
OK, now suppose this large integer is, let's say 10 to the power six and what we are doing.
So this will become 10 to the power 12.
This magenta will become 10 to the power 12.
And this is a very big integer.
And obviously this cannot be stored in an integer variable.
OK, so the one way to handle this problem is basically what you can do is take everything longlong.
OK, use this today, type Longlong, so the range of this is basically ten to the power 18.
OK, so double double of this one.
So this is basically standard operating so long, long will work fine.
Now the second way to solve this problem is what we are doing here is we are writing to Mel and we are
doing multiplication and then we are comparing.
So what we can do, so can we write it like this.
Mid equals equals X divided by mid.
OK, if we will write code like this, then we will not get in digital flight.
OK, because here we are dividing so our number will become smaller.
OK, our number will become smaller and we will not get integer overflow or you can say random error.
So here we are getting overflow see overflow at it.
So if we will write it like this.
This will work fine.
OK, so instead of multiplication.
They will write X divided by mid.
And same for this one.
X divide by mid.
OK, now let's summit it, so hopefully they should work fine.
So, again, we are getting all flooded.
We are getting ready for this line now.
We all know the better way to write this is basically start plus and minus, start by two.
OK, now let's admit.
OK, so now our court is looking for an.
So many times I've already explained this thing.
So START is a big number and is a big number, and the other day you are adding two numbers and then
you are dividing by two.
So when you are adding two very large integer, there is a possibility that it will it cannot be contained
inside an integer variable.
So that's why this is a good way to write and minus to start first subtract that number becomes smaller
and then you can add.
OK, ok, so what is the time and the space complexity.
So we have already discussed since we are using binary search.
So time complexities, Logan and space complexities or the rough one.
OK, so if you have any doubt in this question you can ask me.
OK, thank you.