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:

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

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

Can we do this…

If N & (N-1) == 0:

Yes

Else

No

👌👌👌😃

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.

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 ?

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

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.

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

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

I have sent the

question link before but there was not response by You.

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 .

———————————————————– 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.")

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;

}

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.

how did you arrive at high = 100000?

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

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

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…

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

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

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

}

return false;

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

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;

}

};

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

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

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.

You explain too good.

Would you make videos on codechef long challenges too?

Great Video Techdose keep it up