# Valid Perfect Square | Leetcode #367

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 🙂

Nguồn: https://anniesnannies-seattle.com/

Xem thêm bài viết khác: https://anniesnannies-seattle.com/game/

## 25 thoughts on “Valid Perfect Square | Leetcode #367”

1. rachit bundela says:

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

2. Paras says:

👌👌👌😃

3. yashbeer singh says:

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.

4. Krishna Mohanty says:

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 ?

5. Atharsh Muthu says:

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

6. Smruti Ranjan says:

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.

7. ESudarshan says:

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))

8. creative work says:

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

9. MUNESH SHARMA says:

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

10. MUNESH SHARMA says:

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 .

11. Anuj Vyas says:

———————————————————– Python3 Solution ———————————————————–
def isPerfectSquare(number):

low = 1
high = 100000

while low<=high:
mid = int(low + (high-low)/2)
temp_square = mid*mid
if temp_square == number:
return True
elif temp_square>number:
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.")

12. NITESH AGARWAL says:

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(low<=high){
mid = low+(high-low)/2;
sq = mid*mid;
if(sq==num){
return true;
}else if(sq>num){
high = mid-1;
}else{
low = mid+1;
}

}

return false;

}

13. Evgeni Nabokov says:

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.

14. manoj ks says:

how did you arrive at high = 100000?

15. Ash Winchester says:

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

16. Evgeni Nabokov says:

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

17. spock says:

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…

18. Chunks says:

if (num == 1 || num == 0) return true;

for (int i = num/2; i >= 0; i– ) {

if (i*i == num) return true;

}

return false;

19. Chandan Nayak says:

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

20. Souvik Das says:

This too got accepted at 0 ms runtime :

class Solution {

public:

bool isPerfectSquare(int num) {

for(long int i=0;i*i<=num;i++){

if(i*i==num){

return true;

}

}

return false;

}

};

21. Safalya Ghosh Roy says:

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

22. Rajesh Bammidy says:

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

23. Prajwal D R says:

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.

24. Niranjan hegde says:

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

25. Anil chaudhry says:

Great Video Techdose keep it up