Valid Perfect Square | Leetcode

Подписаться 174 тыс.

Просмотров 16 тыс.

50% 1

This video explains a very interesting programming interview question which is to find if given number N is a perfect square or not. We are not allowed to use any library function like square root function or log function etc to solve this question. There are many ways to solve this question. I have shown 2 methods. The first method takes square root of N time and the optimal approach takes only log(sqrt(N)) time. The space is O(1) for solving this problem. At the end of the video i have explained the CODE for the same. CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.co...

Опубликовано:

11 сен 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 99

@avanishpandey1173 2 года назад

Finally I found one mistake in your explanation 😅 Log ( Sqrt(N)) where N is 10^10 will not be 5 because log will have base 2 as this is binary search so ans will be 5log2(10)

@aeroabrar_31 Год назад

Yes exactly !! :)

@officialspock 4 года назад

Oh my god, this solution is so neat, I was stuck at this last night, now I feel so stupid realizing how simple this solution shows...

@techdose4u 4 года назад

😅

@evgeni-nabokov 4 года назад

I applied Newton's method of finding the root of the equation x^2 - num = 0. I get two approx. float roots (the difference between those < 1). Then I get whole roots by applying floor() to float roots. Then If square any of those makes num, I return true. So no sqroot(), only +, -, *, and /. Note: I can square my roots because I applied floor(), which ensures I will not go out of int 32 range (here I may be wrong, but my solution does not fail). One of the cases is max of int 32 = 2147483647.

@ESudarshan 4 года назад

I think the time complexity is O(log2 n) not O(log2 sqrt(N)) If you give 10000 as input to the program, it iterates ~14 times i.e. log2(10000) neither ~2 i.e. O(log10 sqrt(N)) nor ~6 i.e. O(log2 sqrt(N))

@techdose4u 4 года назад

Well it all depends on Max range of number. Log(sqrt(N)) is true for high values of N while log N is true for values near sqrt(N).

@reettikgoswami3733 4 года назад

I think time complexity is log(N) not log(sqrt(n)).. let assume N=100; log(sqrt(100)) ~ 3 it means we can find the solution in 3 iterations but it's not possible. log(100) ~ 5 . we can actually find the solution in 5 iterations plz correct me if I am wrong

@techdose4u 4 года назад

You are wrong. Don't ever make asymptotic analysis for small values. You should take very large value and see. I took 10^10 and explained the time analysis.

@aeroabrar_31 Год назад

@@techdose4u Here as we are dividing the state space by 2 for every iteration then the Time complexity should be Log(N) base 2 for 10^10 , Log(10^10)base 2 will be 10 * Log(10)base 2 so, as log10 value is 3.3.. there will be 31 (approx) iterations to find the square root. Thank me later !! :)

@andreaschristou6952 3 года назад

I was asked a similar question in an interview. The question was to find the square root of a number with accuracy to 3 decimal places. So only the last approach of the video could work in such a case! The second approach could not work, it would take forever!

@techdose4u 3 года назад

Hmm :O

@ptreeful 2 года назад

How did you search doubles?

@secularph8424 4 года назад

7:39 doesn't binary search complexity in log to the base 2??

@techdose4u 4 года назад

Max value of N is INT_MAX which is 2*10^9. If I assume it 10^10 then the value passed to be verified has largest value of 10^10. Now I took high value as 10^5 (since I know the Max range). So, high is sqrt(N). Now when we apply binary search then total time complexity will be log(sqrt(N)). Is there any confusion?

@raghuveernaraharisetti 4 года назад

@@techdose4u In binary search, for each search we divide/reduce the array to half. So the time complexity is log(N) to base 2. We are doing the same in the above solution. For each iteration reducing the range to half. Since the MAX here is 10^5, shouldn't the time complexity be log(10^5) to base 2 rather than log(10^5) to base 10? I didn't understand how we got base 10 here? can you please explain?

@navneetsingh8779 4 года назад

@@raghuveernaraharisetti hello! Actually the things is, base is of no significance. logBase2(N) is asymptoticly same as logbase10(N) . This happen because any base value is just multiplication of constant with function. So you can write logbase2(N) = Theta(logbase10(N)). Like , N is linear function which is = some_constant multiply with linear function N. I hope you got this. Overall base value is constant and log(N) is logarithmic function. We are here looking Asymptotically equal not mathematically equal.

@Learner010 4 года назад

@@navneetsingh8779 well explained bro...

@techdose4u 4 года назад

I have clearly mentioned in the video about range of numbers we can get. The Max range is integer range. I amd checking using mid*mid with N. I am decreasing the search range from int range to sqrt(int_range). I don't know why many people are asking the same question. I have clearly explained the time complexity analysis.

@safalyaghoshroy2405 4 года назад

It can also be done with binary search which has O(log n).

@techdose4u 4 года назад

Yea....there are many methods to solve it. I have provided code for O(log(sqrt(N)).

@manishsalvi2901 4 года назад

I did iteration of i till n/2 Then perform if((number/i)==i ) Then its a perfect square

@techdose4u 4 года назад

You could have changed your if statement like I explained in video to get sqrt(N) easily.

@muneshSharmagmailcom 4 года назад

Bro you have said that you will make videos on GOOGLE KICKSTART Round A and Round B solutions But you have not post the videos yet. i cannot wait for those videos explained by you , please do as soon as possible. These are also good question for practice for Interview preparation .

@techdose4u 4 года назад

Yes you are correct. I have that in my mind. But currently I am not getting any time at all. I have to give a lot of time for office work too. On top of that, most users requested for may challenge. I can calmly make videos only if I get time. What to do bro.

@prajwal9610 4 года назад

Binary search time complexity is log n base 2. So If n is 10^5 complexity will be log 10^5 base 2 which equals to sqrt(10^5) not 5.

@techdose4u 4 года назад

Bro you are mistaken. Max value of N is INT_MAX which is 2*10^9. If I assume it 10^10 then the value passed to be verified has largest value of 10^10. Now I took high value as 10^5 (since I know the Max range). So, high is sqrt(N). Now when we apply binary search then total time complexity will be log(sqrt(N)). Is there any confusion?

@putintocontext3148 4 года назад

@@techdose4u Search is space is reduced to half (1/2) every time and not to 1/10th. So Prajwal is right

@The85souvikdas 4 года назад

This too got accepted at 0 ms runtime : class Solution { public: bool isPerfectSquare(int num) { for(long int i=0;i*i

@techdose4u 4 года назад

Yes....this is sqrt(N) time algo.

@dipeshdarji6253 4 года назад

we can use simple math formulae, a perfect square is always sum of odd numbers. like, 1 = 1 4 = 1 + 3 9 = 1 + 3 + 5 16 = 1 + 3 + 5 + 7 25 = 1 + 3 + 5 + 7 + 9 and so on.. so whatever number you have given subtract 1, 3, 5, and so on. if you reach 0 then its perfect square otherwise it's not. here it is a simple code for the same. bool isPerfectSquare(int num) { int i = 1; while(num > 0) { num = num - i; i = i + 2; } return num == 0; }

@techdose4u 4 года назад

I don't understand why don't you apply AP Sum formula. The sum of first N off natural numbers is N^2. Just solve it and apply. You solution is O(N) for each query.

@dipeshdarji6253 4 года назад

@@techdose4u Because they mentioned in the problem that try to solve the problem without using sqrt() function, I thought that they might want from us that we can think of how AP and sqrt related to each other.

@smrutiranjan3623 4 года назад

Please correct me if I am wrong, but your solution does not depend on "n" as you have taken high = 10^5. So your time complexity will be O(root(log(10^5))) in the worst-case scenario.

@techdose4u 4 года назад

Yes correct. The time complexity here actually depends on Max value of N. If input value is close to sqrt(N) then time complexity becomes log(N).

@evgeni-nabokov 4 года назад

A solution with calculation n * n may not work due to overflow. Try to pass the max int into your function.

@techdose4u 4 года назад

It will work because I took long int 😅

@Yash-uk8ib 4 года назад

finding log2 will also work... this will be a constant time soln.. approach is to find log2 of given number and store it in k. if k*k==num return true else return false.

@techdose4u 4 года назад

I completely forgot the question. Need to chekc it 😅

@Yash-uk8ib 4 года назад

@@techdose4u may be i am wrong... plzz correct me if so

@niranjanhegde1535 4 года назад

You explain too good. Would you make videos on codechef long challenges too?

@techdose4u 4 года назад

No bro ...I will not get time. I am currently focusing on leetcode for coding interview prep. I will keep uploading some good codeforces questions in between to change the taste. I found codeforces to be better than codechef personally.

@Learner010 4 года назад

@@techdose4u true codeforces have quality problems

@Bunny-yy6fo 2 года назад

Hi, can't we do directly like first let's find root of it and convert it into integer and then check square of it with the given value. Please once see this approach

@anilchaudhry804 4 года назад

Great Video Techdose keep it up

@techdose4u 4 года назад

Thanks :)

@cloud5887 4 года назад

This was an easy question. Solved it with BS like you at first try 😁 Only thing I don’t get is why you set high to 10000 instead of n/2

@StringStack 4 года назад

Setting it to n/2 is not optimal instead @TECH_DOSE explained better that it's high should be sqrt(n).... And though we can't use function so we simply assume one value

@techdose4u 4 года назад

Vaibhav is correct.INT_MAX is upper bound for integer. So sqrt of INT_MAX will be something lower than 10^5. So I took 10^5 to avoid unnecessary complications.

@cloud5887 4 года назад

Thanks

@atharshmuthu2520 4 года назад

But there is this method "digital rooting" which is faster than the binary search method .. if that's not so can you prove it..?

@yashSharma-pe1dp 4 года назад

Sir why we have taken the numbers from 1 to 10 here when n = 16?

@krishnamohanty4858 4 года назад

Hi, Could you please publish a video on painting n house with k number of colors where the adjacent houses should n't have the same color ?

@techdose4u 4 года назад

Will be done later.

@muneshSharmagmailcom 4 года назад

I have sent the question link before but there was not response by You.

@techdose4u 4 года назад

I recieve many requests which I am not able to process due to lack of time. I hope everyone understands that. What question are you talking about?

@dr.ashwini295 4 года назад

👌👌👌😃

@techdose4u 4 года назад

😁

@ChandanNayak-lq1pd 4 года назад

Will leet code and GFG be sufficient for product based company or we need do CP?

@techdose4u 4 года назад

No need for CP. Leetcode itself is sufficient. Just prepare OOPs and theory part as well. Coding questions are asked from leetcode.

@ChandanNayak-lq1pd 4 года назад

@@techdose4u Thank you for reply

@techdose4u 4 года назад

Welcome :)

@harshitsharma5647 3 года назад

Can u tell me why u write in code Mid = low + (high - low)/2

@techdose4u 3 года назад

To find mid index.

@harshitsharma5647 3 года назад

Sir I am not getting this line till now bcz in video u told mid is equal to (low + high) /2 but in code u write something different in mid variable?

@techdose4u 3 года назад

(low+high)/2 may create integer overflow for very large values of low and high. So the one I wrote in code is better. Otherwise they both are fine.

@harshitsharma5647 3 года назад

Thankyou for clear my doubts 🙂.

@techdose4u 3 года назад

Welcome

@aswinikumarsahoo6459 2 года назад

Why has been the high assigned to100000?

@yjj410 4 года назад

python code class Solution: def isPerfectSquare(self, num: int) -> bool: if num=start: if mid**2 == num: return True if mid**2 > num: end = mid-1 mid = (start+end)//2 elif mid**2 < num: start = mid+1 mid = (start+end)//2 return False

@fatimajaffal9843 4 года назад

Nice solutions ,my complexity was n/2 haha :(

@techdose4u 4 года назад

Don't worry. You could have just changed your if statement and improved your time to O(sqrt(N)). Was your solution accepted?

@fatimajaffal9843 4 года назад

@@techdose4u Yes, it was accepted,but it never crossed my mind that we can use i*i rather than n/2 or binary search class Solution { public: bool isPerfectSquare(int num) { if(num == 1) return true; for(long long i=1;i

@techdose4u 4 года назад

Now you got to learn something new which will be very useful :)

@fatimajaffal9843 4 года назад

@@techdose4u Yes, I learned a lot from your channel

@shaurya478 4 года назад

@@fatimajaffal9843 not optimal as binary search

@retrogame3138 4 года назад

10^8 iteration is 1 second?

@techdose4u 4 года назад

Yes you can assume.

@niteshagarwal4934 4 года назад

can you find why it is failing for num =16 public boolean isPerfectSquare(int num) { int low = 1; int high = 100000; int mid = 0; int sq = 0; while(lownum){ high = mid-1; }else{ low = mid+1; } } return false; }

@raginisharma6472 4 года назад

you need to have long as datatype and not int. Because while you are multiplying int's in the loop, it might excced the int limit.

@mks396 4 года назад

how did you arrive at high = 100000?

@techdose4u 4 года назад

Because num has max value of INT_MAX and 10^10 is upper bound for INT_MAX. So, sqrt(10^10) = 10^5.

@mks396 4 года назад

@@techdose4u Got it. We can also init high = num;

@techdose4u 4 года назад

Yes. But time complexity will then be Log(N)

@rachitbundela 4 года назад

Can we do this... If N & (N-1) == 0: Yes Else No

@techdose4u 4 года назад

👍

@b.sainathreddy4567 3 года назад

how it works

@rajeshbammidy180 4 года назад

No matter what BinarySearch drastically decreases the search space and here is the Java soln:github.com/RajeshAatrayan/InterviewPreparation/blob/master/src/BinarySearch/IsPerfectSquare.java

@techdose4u 4 года назад

Thanks for sharing

@rajeshbammidy180 4 года назад

@@techdose4u Are you using your tab or something to draw(sketch) the things on the screen or you are using your mouse?

@chunks1796 4 года назад

if (num == 1 || num == 0) return true; for (int i = num/2; i >= 0; i-- ) { if (i*i == num) return true; } return false;

@anujvyas9493 4 года назад

----------------------------------------------------------- Python3 Solution ----------------------------------------------------------- def isPerfectSquare(number): low = 1 high = 100000 while lownumber: high = mid-1 else: low = mid+1 return False if __name__ == '__main__': number = int(input('Enter a number between 1 and 10^10: ')) boolean_value = isPerfectSquare(number) if boolean_value: print("It's a perfect square!") else: print("Not a perfect square.")