My Weblog

Blog about programming and math

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
       {
         BufferedReader stdin= new BufferedReader(new InputStreamReader(System.in));
         String s_1=stdin.readLine();
         int n=Integer.parseInt(s_1);
        
         
         boolean  f=false;
         for(int i=0;i<n;i++)
         {
            if(f)System.out.println();
            f=true;
            stdin.readLine();//for blank line
            String    s_2=stdin.readLine();
            BigInteger x=new BigInteger(s_2);
            BigInteger x_0,x_1=x,div=new BigInteger("2");
            do
            {
                x_0=x_1;
                x_1=x_0.add(x.divide(x_0)).divide(div);

            }while(x_0.compareTo(x_1)!=0);
            System.out.println(x_1);
          
            
            /* BigInteger lo=BigInteger.ZERO,hi=x,mid;
            while(lo.compareTo(hi)<0)
            {
               mid=(lo.add(hi)).divide(new BigInteger("2"));
               BigInteger res=mid.pow(2);
               if(res.compareTo(x)<0) lo=mid.add(new BigInteger("1"));
               else hi=mid;

            }
            mid=(lo.add(hi)).divide(new BigInteger("2"));
            //System.out.println(lo+" "+mid+" "+hi+" "+mid.pow(2));
            System.out.println(mid);*/
          
         }

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

}

Advertisements

October 2, 2010 - Posted by | Programming

4 Comments »

  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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: