CareerCup

If you cannot use floating point approximations, do binary search.

Just keep adding odd numbers.

0+1=1
1+3=4 etc etc
-------------------

int count  = 0;
int oddInteger = 1; //So, odd integer will be 1, then 3, then 5, then 7, etc etc

while(count <= N){
	if(count == N){
		return true;
	}

	count = count + oddInteger;
	oddInteger = oddInteger + 2;
}

Runs in O(Sqrt(n)) time I believe.

bool isPerfectSquare(int N)
{
	for(int i=0; i*i <= N; i++)
		if(i*i == N)
			return true;
	return false;
}

binary search of (0, x / 2)

bool is_sqrt_helper(int x, int from, int to)
{                                           
  if (to < from) return false;              

  int mid = (from + to) / 2;

  int r = mid * mid;
                    
  if (from == to)
    return r == x;

  if (r > x)
  {
    return is_sqrt_helper(x, from, mid - 1);
  }
  else if (r < x)
  {
    return is_sqrt_helper(x, mid + 1, to);
  }
  else
  {
    return true;
  }
}

bool is_sqrt(int x)
{
  if (x == 0 || x == 1) return true;
  return is_sqrt_helper(x, 0, x / 2);
}

Here is what I would do in python

i = int(raw_input())

sq = int(i ** 0.5)

if sq*sq == i:
    print i
    print "It is a perfect Square"
else:
    print i
    print "It is not a perfect Square"

{ float x = n;
float y = 1;
float e = 0.000001; /* e decides the accuracy level*/
while(x - y > e)
{
x = (x + y)/2;
y = n/x;
}
return x; }

it is Babylonian method for fiinding square root

/*code in C*/
for(i=1;i<n;i++)
{ if (i*i==n)
{ printf("perfect square");}
else
{ printf("Not a perfect square");}
}

Here is code in C#.. I have used uint to make sure N is not negative as square can never be negative. Also if N is 0 return false

private static bool isSquare(uint N)
        {
            if (N == 0)
            {
                return false;
            }
            for (int i = 1; i * i <= N; i++)
            {
                if (i * i == N)
                {
                    return true;
                }
            }
                return false;
        }

int main()
{
int k=0,n,i=1;
cout<<"enter any number:\n";
cin>>n;
if(n==0||n==1)
cout<<"squre root of entered number:"<<n;
else
{
for(i=1;i*i<=n;i++)
{
if(i*i==n)
cout<<"squre root of entered number:"<<i;
k=1;
}
}
if(k==0)
cout<<"entered number dont have perfect squre root:";
return 0;

}

int main()
{
int k=0,n,i=1;
cout<<"enter any number:\n";
cin>>n;
if(n==0||n==1)
cout<<"squre root of entered number:"<<n;
else
{
for(i=1;i*i<=n;i++)
{
if(i*i==n)
cout<<"squre root of entered number:"<<i;
k=1;
}
}
if(k==0)
cout<<"entered number dont have perfect squre root:";
return 0;

}

Forgot to mention the constraint. solution should work in O(N) time.

This junk site not allowing to edit existing questions. Sorry for the late clarifications.

/*
	This will run in logarithmic time.
	 */
	public boolean isPerfectSquare(Integer input) {

		// note - this method ignores the possibility of integer overflwo.
		boolean flag = false;
		int value = 1;

		// the number we multiply the upperlimit with as we search for the
		// limits that bound the input from above and from below.
		int factor = 2;

		// the limits that bound the input from above and below
		int lowerLimit = 0;
		int upperLimit = 1;

		// determine the limits within which binary search is to be done.
		while (input > upperLimit * upperLimit) {
			lowerLimit = upperLimit;
			upperLimit = upperLimit * factor;
		}

		// the do th binary search
		if (!flag) {
			while (lowerLimit < upperLimit) {
				value = (lowerLimit + upperLimit) / 2;
				int valueSquare = value * value;
				if (valueSquare > input) {
					upperLimit = value-1;
				}
				else if (valueSquare < input) {
					lowerLimit = value+1;
				}
				else {
					flag = true;
					break;
				}
			}
		}

		return (flag);
	}

The below code runs in O(logN) time.

bool isSqrRoot(int n)
{
	for(int i=1;i<n/2;i++)
	{
		if((i*i)==n)
			return true;
	}
		return false;

}

log base 2(N) is O(root(n)) .so it log base 2.however generic representation is O(n^0.5).

#include<stdlib.h>
#include<stdio.h>
void main()
{
int a,i;
printf("enter number:--");
scanf("%d",&a);
for(i=0;i*i>a;i=i/2);
for(;;)
{
if(i*i==a)
{
printf("perfect square\n");
exit(0);
}
if(i*i>a)
break;
i++;
}
printf("not perfect square\n");
}

Couldn't you find the fast inverse square root and then find the reciprocal of that?

www . codemaestro . com / reviews / 9

Single function, called once. O(1).

#include<stdio.h>
#include<conio.h>
int main()
{
int i,N;
printf("enter the number you want to check.\n");
scanf("%d",&N);
for(i=1;i<=N;i++)
{
if(N=i*i)
printf("the number is a perfect square.");
else
printf("the number entered is not a perfect square.");
}
return (0);
}

public class PerfectSquare {

public static void main(String[] args) {
int n= 144;
PerfectSquare ins = new PerfectSquare();
System.out.println("is "+n+" is perfect square : "+ins.isPerfectSquare(n));
}

public boolean isPerfectSquare(int n){
for(int i=0;i*i <=n;i++){
if(i*i == n){
return true;
}
}
return false;
}

}

#!/bin/python3

def perfect_square(n):
	square = n ** 0.5
	return square * square == n

static void Main(string[] args)
{
Console.WriteLine("Result = " + calcSQRT(2)); //Test Call;
Console.WriteLine("End");
}

static Double calcSQRT(int square, int overAllPrecision = 32)
{

int[] pairArray = getPairsArray(square);
String resultBuffer = "";



int currentIndex = 0;
BigInteger A = new BigInteger(pairArray[pairArray.Length - currentIndex - 1]);//BigInteger is from the System.Numerics
BigInteger y = new BigInteger(0);
while (true)
{
int i = 0;
while ((A - (10 * y + 2 * (i + 1) - 1)) >= 0)
{
i++;
A = A - (10 * y + 2 * i - 1);

}

if (currentIndex == pairArray.Length)
resultBuffer = resultBuffer + ".";

resultBuffer = resultBuffer + i;
currentIndex++;


if (currentIndex > overAllPrecision) break;

if (A == 0)
if (currentIndex >= pairArray.Length)
break;
A = 100 * A;
if (currentIndex < pairArray.Length)
A = A + pairArray[pairArray.Length - currentIndex - 1];

if (currentIndex == 1)
y = 2 * i;
else
y = 10 * y + 2 * i;
}

return Double.Parse(resultBuffer);

}

private static int[] getPairsArray(int square)
{
int[] pair = new int[1];
int count = 0;
while(square > 0)
{

int digit = square % 10;
square = square / 10;
if(square > 0)
{
digit = (square % 10) * 10 + digit;
square = square / 10;
}
if (count > 0)
Array.Resize(ref pair, count + 1);
pair[count] = digit;
count++;
}
return pair;
}

static void Main(string[] args)
        {
            Console.WriteLine("Result = " + calcSQRT(2)); //Test Call;
            Console.WriteLine("End");
        }

        static Double calcSQRT(int square, int overAllPrecision = 32)
        {

            int[] pairArray = getPairsArray(square);
            String resultBuffer = "";



            int currentIndex = 0;
            BigInteger A = new BigInteger(pairArray[pairArray.Length - currentIndex - 1]);//BigInteger is from the System.Numerics
            BigInteger y = new BigInteger(0);
            while (true)
            {
                int i = 0;
                while ((A - (10 * y + 2 * (i + 1) - 1)) >= 0)
                {
                    i++;
                    A = A - (10 * y + 2 * i - 1);

                }

                if (currentIndex == pairArray.Length)
                    resultBuffer = resultBuffer + ".";

                resultBuffer = resultBuffer + i;
                currentIndex++;


                if (currentIndex > overAllPrecision) break;

                if (A == 0)
                    if (currentIndex >= pairArray.Length)
                        break;
                A = 100 * A;
                if (currentIndex < pairArray.Length)
                    A = A + pairArray[pairArray.Length - currentIndex - 1];

                if (currentIndex == 1)
                    y = 2 * i;
                else
                    y = 10 * y + 2 * i;
            }

            return Double.Parse(resultBuffer);

        }

        private static int[] getPairsArray(int square)
        {
            int[] pair = new int[1];
            int count = 0;
            while(square > 0)
            {
                
                int digit = square % 10;
                square = square / 10;
                if(square > 0)
                {
                    digit = (square % 10) * 10 + digit;
                    square = square / 10;
                }
                if (count > 0)
                    Array.Resize(ref pair, count + 1);
                pair[count] = digit;
                count++;
            }
            return pair;
        }

public boolean isPerfectSquare(int n) {
		int sum = 0;
		if(n == 0 || n<0) {
			return false;
		}
		else if(n ==1){
			return true;
		}
		else {
			for(int i=1;i<n;i+=2){
				sum = sum+i;
				if(sum == n)
				{
					return true;
				}   
			}
			return false;
		}
	}