Number problems are abound in the programming interview world. A perfect square (also called a square number) is an integer that is the square of an integer; in other words, it is the product of some integer with itself. So, for example, 9 is a square number, since it can be written as 3 × 3. So are 16, 25, 49 and so on.

So how do we find if a given number is a square number or not? There are a many ways. This is a big research topic in the mathematics world. For the purpose of interview, we will not delve into highly complex solutions.

A **bad implementation** would be something like this:

public static bool IsSquare(long target)

{

// loop through all the numbers till the target

for (long i = 0; i < target; i++)

{

// if we have a match

if ((i * i) == target)

{

return true;

}

}

// no matching number could be squared

return false;

}

This is an inefficient solution. There is no need to loop till the element. The only case when this would be true is 1. Beyond that, if a number is a square, it’s square root has to be less than half of the number (4 – 2, 9 – 3, 16 – 4, 25 – 5 an so on. Let’s modify our algorithm to add this logic.

**Still a bad implementation**:

public static bool IsSquare(long target)

{

// loop through HALF the numbers till the target

for (long i = 0; i < target/2; i++)

{

// if we have a match

if ((i * i) == target)

{

return true;

}

}

// no matching number could be squared

return false;

}

Even though we have cut our loop by half, this is still inefficient. So what can we do more to stop the loop earlier. Let’s assume that our target number was 20. So using the code above, we will be looping till 10. Now once the loop crosses 5, we know that none of the numbers above that will result in the loop being true. So, a good condition to add would be break if the square of the current number is greater than the target. Let’s review this code below:

public static bool IsSquare(long target)

{

// handle 0 and 1

if (target <= 1)

return true;

long currentSquare = 4;

long currentNumber = 2;

// loop through till the target is more than

// the square of the current number

while (currentSquare <= target)

{

// if we have a match, return true

if (currentSquare == target)

return true;

// increment current number

currentNumber++;

// find the next square

currentSquare = currentNumber * currentNumber;

}

// no matching number could be squared

return false;

}

Yes, this is still not the best solution but these code snippets should give you a good enough idea on how to optimize this algorithm further. I challenge the readers to take a few minutes out and come up with a better solution.

Im a kid. How would you explain it to me?

ReplyDeleteboova saappudu chellam.....:)

DeleteAdd a check if the number does not end with 0,1,4,5,9 return false;

ReplyDeletethen 16 isnt a square. Idiot. :|

DeleteYou guys are trying way to hard.

ReplyDeletepublic static bool IsSquare(long target)

{

return Math.Sqrt((double)target) % 1d == 0d;

}

seems good :)

Deleteyes it is good.But without using built in functions..

Deletewe need top go in other way that i Need .Thanks in advance

@Jacob

DeleteThe point is in programming interviews you'll be asked not to used libraries. Otherwise, if the interviewer asks you to write a function for binary search, you could write:

return System.Array.BinarySearch(...);

Hahaha!

poda daiiiiiiii

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteDear Nikhil Singhal,

ReplyDeleteIs he following a better solution in terms of efficiency??

Thank you.

int x;

bool flag=false;

cin>>x;

for (int i=2;i < x/2;i++)

{

if(x%i==0)

{

if (i*i==x)

{

flag=true;

break;

}

}

}

if(flag) cout<<"Perfect square";

else cout<>x;

You could do a binary search instead. Start with i = median(n). Then compare i^2 with n to determine which direction to go. Repeat until you have an i value such that i^2 == n or until you've exhausted all viable possibilities. Run-time is O(lg n) assuming multiplication is a constant-time operation.

ReplyDeleteThanks. That really helped. Using a Binary Search never occured to me :)

Deletethis is not bad:

ReplyDeleteprivate static bool IsSquare(long value)

{

double temp = Math.Sqrt(value);

return unchecked(temp == (int)temp);

}

sir, May i know how exact compare does between temp and int(temp), what double temp variable will stores.?

Deletewhat about (x & (x-1)) == 0 ?

ReplyDeletethis is for checking if no. is a power of 2 or not

Deletebool isPerfectSquare(long input)

ReplyDelete{

// return true for trivial cases

if( input == 0 || input == 1)

{

return true;

}

else if( input == -1)

{

return false;

}

// make an initial guess and store as a floating point.

// the divisor is arbitrary, testing would have to be done to choose an optimal value

// basically the closer the initial value the faster the solution

double guess = input /2.0;

// uses approximation equation for 20 iterations or until the guess is close enough

// the max number of iterations could be adjusted

for(int i = 0; i < 20; i++)

{

// if the guess, is correct it will exit the loop.

if( guess * guess == input)

{

return true;

}

guess = 1.0/2.0 *( guess + input/guess);

}

return false;

}

public static boolean isSquare(int n)

ReplyDelete{

int k=1;

while (n!=0)

{

if (n<0)

return false;

else

{

n=n-k;

k+=2;

}

}

return true;

}

This could be solved in a constant time O(C), given that integers have fixed bit-size. Digit-by-digit algorithm will have O(M) complexity, where M is number of bits in integer. Still the implementation is somewhat complicated.

ReplyDeletepublic static bool isPerfectSquare(long target)

ReplyDelete{

long result,perfSquare = target / 2;

do{

result = perfSquare * perfSquare;

if (result == target)

return true;

else if (target < result)

perfSquare = perfSquare - 1;

else

perfSquare = perfSquare / 2;

}while(target<result);

return false;

}

your looping as normal from half

DeleteExample : for 25 , your looping from 12,11,10.....5 (7 times)

programming should change to

public static bool isPerfectSquare(long target)

{

long result,perfSquare = target / 2;

do{

result = perfSquare * perfSquare;

if (result == target)

return true;

else if (result > target)

perfSquare = perfSquare / 2;

else

{

perfSquare = perfSquare * 2 - 1;

result = perfSquare * perfSquare;

if (result == target)

return true;

}

}while(target<result);

return false;

}

This allows to loop around values for 25 (12,6,3 then 5 result) 3 times..

One can keep adding odd integers starting from 1, until the sum matches the number (ansewer=yes) or exceedes (answer=no).

ReplyDelete1 = 1^2

1+3 = 2^2

1+3+5 = 3^2

....

This is still a linear solution but addition is cheaper than multiplication.

public static bool IsSquare(int target)

ReplyDelete{

for (int i = 0; i <= Math.Sqrt(target); i++)

{

System.Console.WriteLine(Math.Sqrt(target));

if (i * i == target)

{

return true;

}

}

return false;

}

better?

Here is how I did it using Binary Search.

ReplyDeleteCall the initial Binary Search with start =1;end = OriginalNumber/2 ; and original = OriginalNumber

bool binarySearch(long start,long end,long original)

{

long mid = (start + end) / 2;

if (original == 1)

return true;

if (mid * mid == original) { return true; }

if (start >= end)

return false;

if (mid * mid < original)

return binarySearch(mid + 1, end, original);

else

return binarySearch(start, mid - 1, original);

}

I am glad it helped you

Delete