Monday, 28 December 2015

Big Integer Implementation

// Big Integer Implementation

#include "bits/stdc++.h"
using namespace std;
#define pb                       push_back
#define all(v)                   v.begin(),v.end()

// Excluding leading zeroes
string roundzero(string x){
    string ans="";
    int flag=1;
    if(x[0]-'0'!=0) flag=0;
    int i;
    for(i=0;i<x.length()-1 && flag==1;i++){
        if(x[i]-'0'!=0) flag=0;
    }
    for(int j=i;j<x.length();j++){
        ans.pb(x[j]);
    }
    return ans;
}

// To find greater of two string
int greater1(string x,string y){
   int i=0;
   while(x[i]==y[i] && i<x.size()){
    i++;
   }
   if(i==x.size()) return -1;
   if(x[i]-'0'>y[i]-'0') return 1;
   else return 0;
}

// To make strings of equal length
vector<string> equallength(string x,string y){
    //if(x.size()==y.size()) return;
    if(x.size()>y.size()){
        string temp1=x,temp2=y;
        reverse(all(temp1));
        reverse(all(temp2));
        int u=x.size()-y.size();
        while(u--){
            temp2.pb('0');
        }
        reverse(all(temp1));
        reverse(all(temp2));
        x=temp1;
        y=temp2;
    }
    if(y.size()>x.size()){
        string temp1=x,temp2=y;
        reverse(all(temp1));
        reverse(all(temp2));
        int u=y.size()-x.size();
        while(u--){
            temp1.pb('0');
        }
        reverse(all(temp1));
        reverse(all(temp2));
        x=temp1;
        y=temp2;
    }
    vector<string> ans;
    ans.pb(x);
    ans.pb(y);
    return ans;
}
//ADD
string add(string x,string y){
       string ans="";
       vector<string> el=equallength(x,y);
       x=el[0];
       y=el[1];
       int carry=0;
       for(int i=x.size()-1;i>=0;i--){
           //cout<<(((x[i]-'0')+(y[i]-'0')+carry)%10)<<endl;
         int ans1=(((x[i]-'0')+(y[i]-'0')+carry)%10);
         ans.pb((char)(ans1+48));
         carry=(x[i]-'0'+y[i]-'0'+carry)/10;
       }
    if(carry!=0)
    ans.pb((char)(carry+48));
    reverse(all(ans));
    return ans;
}
//SUBTRACT
string subtract(string x,string y){
    string ans="";
    vector<string> el=equallength(x,y);
    x=el[0];
    y=el[1];
    //cout<<x<<" "<<y<<endl;
    int flag=greater1(x,y);
    //cout<<flag<<endl;
        if(!flag)
        {
            string temp=x;
            x=y;
            y=temp;
        }
        for(int i=x.size()-1;i>=0;i--){
            if(x[i]-y[i]>=0){
                ans.pb((char)(48+x[i]-y[i]));
            }
            else{
              int r=i-1;
              while(x[r]=='0') r--;
              x[r]=x[r]-1;
              for(int k=r+1;k<i;k++){
                x[k]='9';
              }
              int p=10+(x[i]-'0');
              int q=y[i]-'0';
              ans.pb((char)(48+(p-q)));
            }
            //cout<<x<<" "<<y<<" "<<ans<<endl;
        }
    reverse(all(ans));
    return ans;

}
//MULTIPLY
string multiply(string x,string y){
   string ans="";
   for(int i=y.size()-1;i>=0;i--){
    string temp="";
    int e=y.size()-1-i;;
    while(e--) temp.pb('0');
    int p=y[i]-'0';
    int carry=0;
    //cout<<y[i]<<" ";
    for(int j=x.size()-1;j>=0;j--){
        //cout<<x[i]<<" ";
        int q=x[j]-'0';
        int y=((p*q)+carry)%10;
        carry=((p*q)+carry)/10;
        cout<<carry<<" ";
        temp.pb((char)(y+48));
    }
    if(carry!=0)temp.pb((char)(carry+48));
    reverse(all(temp));
    cout<<temp<<endl;
   // cout<<temp<<endl;
    if(ans==""){
        ans=temp;
    }
    else{
        vector<string> el=equallength(temp,ans);
        temp=el[0],ans=el[1];
        ans=add(temp,ans);
    }
   }
   return ans;
}
//DIVIDE  uses repeated subtraction ;;may lead to TLE
vector<string> divide(string x,string y){
     vector<string> ans;
     vector<string> el=equallength(x,y);
     x=el[0];
     y=el[1];
     string qui="",rem="";
   
     if(greater1(x,y)==0) {
             qui.pb('0');
             for(int i=0;i<x.length();i++){
                 rem.pb(x[i]);
             }
     }
     else{
         long long w=0;
         string divid=x;
         string divis=y;
         while(greater1(divid,divis)){
             divid=subtract(divid,divis);
             w++;
         }
         while(w){
             qui.pb((char)(48+(w%10)));
             w/=10;
         }
         reverse(all(qui));
         for(int i=0;i<divid.length();i++){
             rem.pb(divid[i]);
         }
     }
     ans.pb(qui);
     cout<<roundzero(rem)<<endl;
     rem=roundzero(rem);
     ans.pb(rem);
     return ans;
}

//Main
int main(){
   string x,y;
   cin>>x>>y;
   vector<string> ans=divide(x,y);
   cout<<ans[0]<<" "<<ans[1]<<endl;
return 0;
}


Link To Clipboard

No comments:

Post a Comment