# My Weblog

## UVA Online Judge Problem 10023 – Square root

I first approach to this problem when i was learning programming in my first year and i coded this problem in c about 200 lines but that program got time limit exceed. Today i tried with Java and finally succeed. This wiki page has simple algorithm to calculate square root of integers. This code also includes binary search method but it got time limit exceed. Anyway it is still very useful method for many other problem. A glitch in this problem is input format which does not mention clearly how input appears. The input format is
>3
>
>4
>
>9
>
>39898943
and output is
>2
>
>3
>
>6316

```/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

//package uvaproblem_10023;
import java.io.*;
import java.math.BigInteger;

/**
*
* @author user
*/
public class Main {

public static void main(String[] args) /*throws NumberFormatException,IOException*/  {
try
{
int n=Integer.parseInt(s_1);

boolean  f=false;
for(int i=0;i<n;i++)
{
if(f)System.out.println();
f=true;
BigInteger x=new BigInteger(s_2);
BigInteger x_0,x_1=x,div=new BigInteger("2");
do
{
x_0=x_1;

}while(x_0.compareTo(x_1)!=0);
System.out.println(x_1);

/* BigInteger lo=BigInteger.ZERO,hi=x,mid;
while(lo.compareTo(hi)<0)
{
BigInteger res=mid.pow(2);
else hi=mid;

}
//System.out.println(lo+" "+mid+" "+hi+" "+mid.pow(2));
System.out.println(mid);*/

}

}catch (NumberFormatException e){}
catch(IOException e){}
}

}

```

October 2, 2010 - Posted by | Programming

1. There is similar problem on SPOJ ( http://www.spoj.pl/problems/SQRROOT/) but java is not allowed.
Here is methods of square root computation is discussed. http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
Well it might be challenging to implement BigInteger divison in C++ , you can always go for what taught earlier. ( Digit-by-digit calculation )

Comment by divyanshu | October 2, 2010 | Reply

• Actually this c code got time limit exceed on uva but got accepted on spoj . Indeed it was a big challenge specially in first year :D.

```#include<stdio.h>
#include<string.h>
void initialize(char* ,char* , int);
int fun(char* ,char* ,int  );
void  fun1(char* ,int );
void fun2(char* ,char* ,int  );

main()
{

int i,j,l,k,q,x,v,n;
char a[1001],s[1001],d[1001],ch;

scanf("%d",&n);
//scanf("%c",&ch);
for(j=0;j<n;j++)
{
//	scanf("%c",&ch);
scanf("\n%s\n",a);
l=strlen(a);
for(i=0;i<l;i++)
a[i]=a[i]-'0';
for(i=0;i<1001;i++)
d[i]=0;
if(l%2==0)
k=1;
else
k=0;
if(k==0 && a[0]==9)
{
for(i=l;i>=1;i--)
a[i]=a[i-1];
a[0]=0;
l=l+1;
k=1;
}
q=0;
initialize(d,s,q);
while(k!=l+1)
{
initialize(d,s,q-1);
for(i=0;i<=9;i++)
{
fun1(s,i);
v=fun(a,s,k);
initialize(d,s,q-1);
if(v==-1)
break;
}

i--;
fun1(s,i);
fun2(a,s,k);

k=k+2;
d[q++]=i;
}

for(x=0;x<q;x++)
printf("%d",d[x]);
printf("\n\n");
}

}

void initialize(char* d,char* s,int q)
{

int i;
for(i=q;i>=0;i--)
s[q-i]=d[i];
for(i=q+1;i<1001;i++)
s[i]=0;

}

int fun(char* a,char* s,int k)
{

int i,v=0;

for(i=k;i>=0;i--)
{
if(a[i]-s[k-i]+v<0)
v=-1;
else
v=0;
}
return(v);
}

void fun2(char* a,char* s,int k)
{

int i,v=0;
char p;
for(i=k;i>=0;i--)
{

p=(a[i]-s[k-i]+v+10)%10;

if(a[i]-s[k-i]+v<0)
v=-1;
else
v=0;
a[i]=p;
}

}

void  fun1(char* s,int i)
{

int w,p=0,g;

for(w=0;w<1001;w++)
{
s[w]=s[w]*2+p;
if(s[w]>9)
{
p=s[w]/10;
s[w]=s[w]%10;
}
else
p=0;
}
for(w=1000;w>=1;w--)
s[w]=s[w-1];
s[0]=0;
p=0;
s[0]=s[0]+i;
for(w=0;w<1000;w++)
{

if(s[w]>9)
{
p=s[w]/10;
s[w]=s[w]%10;
s[w+1]=s[w+1]+p;
}
else
p=0;
}

p=0;
for(w=0;w<1001;w++)
{
s[w]=s[w]*i+p;
if(s[w]>9)
{
p=s[w]/10;
s[w]=s[w]%10;
}
else
p=0;
}

}

```

Comment by tiwari_mukesh | October 2, 2010 | Reply

2. #include
#include
int main()
{
int n,i;
unsigned long int y,x;
while(scanf(“%d”,&n)!=EOF)
{
printf(“\n”);
for(i=1;i<=n;i++)
{
scanf("%lu",&y);
x=sqrt(y);
printf("\n");
printf("%lu",x);
}
}
return 0;}

Comment by shanto | June 24, 2011 | Reply

3. why this code does not accepted .i don’t know.can you help me
#include
#include
int main()
{
int n,i;
unsigned long int y,x;
while(scanf(“%d”,&n)!=EOF)
{
printf(“\n”);
for(i=1;i<=n;i++)
{
scanf("%lu",&y);
x=sqrt(y);
printf("\n");
printf("%lu",x);
}
}
return 0;}

Comment by shanto | June 24, 2011 | Reply