CareerCup

int PerfectSquareOrNot(int number)
{
int high = number/2;
int low = 0;
while(high>=low)
{
int mid = (low + high)/2;
int square = mid * mid;
if(square==number)
{
return mid;
}
if(square > number)
{
high = mid-1;
}
else
{
low = mid+1;
}
}
return 0;
}
//Binary search... O(log n)

You can prestore all the squares of all the numbers from 1 to large_number and finding out whether the number is square root or not will be just a matter of searching it in that array or where ever you store.
Note:this will take a lot of space.

You could also halve the input number and do a binary search of the squares of the lower half. This would give you nlogn growth.

Question continued : Inbuilt squareroot function should not be used

(Disclaimer: I'm really sleepy right now, so there might be some small errors here. But the general algorithm feels right to me. If I'm wrong, then of course please point it out. :-) )

Any negative numbers can be immediately eliminated. You can also eliminate 40% of the positive numbers right away by checking the value of N % 10. Any numbers ending in 2, 3, 7, or 8 are guaranteed to not be squares (the leastmost digit is guaranteed to be the leastmost digit resulting from multiplying 0*0, 1*1, 2*2, etc. up to 9*9).

Here's my O(log n) solution for the rest. Count the number of bits in N through bit-shifting and halve it (round down). Let's call that P. Have a divisor variable, D, and initialize it to the value of 2^P. Divide N by D. If the result is D, you're done. If the result is different, set P=P-1. If the result is less than D, set D = D - 2^P. If the result is more than D, set D = D + 2^P. Run the new division. Repeat until you either get a result of D or you get a result different from D after P = 0. If the latter, it's not a square.

For example, let's say N = 27. So that means P = 2. So first we divide 27 by 4 (2^2). The result is 6.75, which is more than 4. So next we divide by 6 (2^2 + 2^1). The result is 4.5, which is less than 6. So next we divide by 5 (2^2 + 2^1 - 2^0). The result is not 5, so we state that 27 is not a perfect square.

divid the input through prime numbers starting from 2 recursively till a number divid it , if it gets divided then divid it again by it , if result does not get divide then its not square and if it does continue the process till it doesn't.

1 = 1
4 = 1 + (1 + 2 * 1)
9 = 4 + (1 + 2 * 2)
16 = 9 + (1 + 2 * 3)
Continue this series
if you reach exactly n then n is perfect square
but if you reach > n, then n is not perfect square

O(root n)

//algorithm is based upon basic technique of finding sqaure root of a given number
#include <iostream>
#include <vector>

using namespace std;

int a[]={0,1,2,3,4,5,6,7,9,10};
#define MAX_DIGITS_INPUT              1000
#define NUM_DEC_DIGITS                11


int ValnCountInputDigits(char *input, int* digits){
    int i=0;
    
    if (!input || !digits)
       return 0;

    while(isdigit(input[i]))
       i++;
        
    if (i==0)
       return 0;
       
    if(input[i] !='\0')
       return 0;
    
    else {
         *digits = i;
         return 1;
    }
}


int calroot(char *root, int n,unsigned int *result){
    int isodd =0, both_zero = 0,min;
    unsigned int div,temp_div, prev_div;
    unsigned int res;
    int i,j=0,k=0,l;
    unsigned int quo=0;
    unsigned int rem; 
    unsigned int temp_no=0,temp_no1=0;
    if (!root || !n)
    {
       *result=0;      
       return 1;
    }
    if (!result) 
       return 1;
    if (n & 1)
       isodd=1;
    if (root[0] == '-') {
          *result=0;      
          return 1;
       }
    div=a[0];   
     while(j<n) {
      temp_no1=0;          
      temp_no1+=root[j]-'0';
      j++;
      if (!isodd) {
         temp_no1=10*temp_no1+(root[j]-'0');
         if (root[j]-'0' == 0 && root[j-1]-'0'==0)
            both_zero=1;
         j++;
      }
      isodd =0;
      temp_no+=temp_no1;
      min =-1;
      div=div*10;
      temp_div=div;
      
      if (!both_zero) {
         for (i=0;i < NUM_DEC_DIGITS; i++){
          
             temp_div+=a[i];
             if((temp_div*a[i])<=temp_no) {
                 min=temp_div+a[i];
                 l=i;
                 prev_div=temp_div;
             }
             else
                  break;
             temp_div-=a[i];
          }
          div=min;
          quo=quo*10+a[l];
          temp_no=temp_no-prev_div*a[l];
          temp_no*=10;

          if(!isodd)
              temp_no*=10;
      } else {
        div=div*10;
        quo=quo*10;
      }
      k++;
    }
    if (temp_no == 0){
     *result = quo;
     return 0;
    }
    return 1;
}

int main(int argc, char *argv[])
{
    unsigned int result;
    char arr[MAX_DIGITS_INPUT];
    unsigned int temp;
    int  ret;
    int digits;
    
    cout<<"Enter you input"<<endl;
    cin.getline(arr,MAX_DIGITS_INPUT,'\n');
    ret = ValnCountInputDigits(arr, &digits);
    if (ret == 0) {
       cout<<"input is invalid\n";
       system("PAUSE");
       return EXIT_SUCCESS;
    }
    ret=calroot(arr, digits, &result);
    if (!ret)
       cout<<"number perfect square, sqaure root  "<<result<<endl;
    else 
        cout<<"number not perfect square"<<endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}