UVA-10220 (I love Big Number)

Here is full code:

// UVA ID - 10220 I Love Big Numbers

import java.util.Scanner;
import java.math.BigInteger;

class Main {

    public static void main(String args[])
    {
        Scanner scr = new Scanner(System.in);

        BigInteger fact[] = new BigInteger[1001];
        fact[1] = BigInteger.ONE;

        for(int i=2; i<=1000; i++)
            fact[i] = fact[i-1].multiply(BigInteger.valueOf(i));    

        while(scr.hasNextInt()) {
            int N = scr.nextInt();

            BigInteger F = fact[N];
            BigInteger sum = BigInteger.ZERO;

            while( ! F.equals(BigInteger.ZERO)) {
                            sum = sum.add(F.mod(BigInteger.TEN));
                            F = F.divide(BigInteger.TEN);
                        }

                        System.out.println(sum);
        }
    }
}

Here is CPP solution:

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

#define maxlength 645
#define max(a,b) ((a) > (b) ? (a) : (b))

class Mbigint {
public:
    int length;
    int digit[maxlength];

    Mbigint(int=0);
    ~Mbigint() {}
    void checklength();
    void operator=(long M);
    void operator=(char *str);
    void operator=(Mbigint M);
    Mbigint operator+(Mbigint M);
    Mbigint operator*(Mbigint M);
    Mbigint operator*(int M);
    Mbigint operator/(int M);
    Mbigint operator%(int M);

    bool operator<(Mbigint M);
    bool operator<=(Mbigint M);
    bool operator>(Mbigint M);
    bool operator>=(Mbigint M);
    bool operator==(Mbigint M);
    bool operator!=(Mbigint M);

};

void show(Mbigint M);

Mbigint::Mbigint(int v)
{
    (*this)=v;
    //this->checklength();
}

void Mbigint::checklength()
{
 for(;length>0 && digit[length]==0;length--);
}

void Mbigint::operator=(long M)
{
    memset(digit,0, maxlength*sizeof(int));

    for(length=0; M!=0; M /= 10000)
        digit[++length] = M % 10000;
    checklength();
}

void Mbigint::operator=(char *str)
{
    int L = strlen(str), temp = 0, i, j, k;
    length = (L + 3)/4;

    for(i=0;i < L%4; i++)
        temp = temp * 10 + (str[i] - '0');

    digit[length] = temp;

    j=0;
    if(L%4==0) k = length;
    else k = length - 1;
    temp = 0;
    for(i=L%4; i<L; i++) {
        temp = temp * 10 + (str[i] - '0');
        j++;
        if(j%4==0) {
            digit[k--] = temp;
            temp =0;
            j=0;
        }
    }
}

void Mbigint::operator=(Mbigint M)
{
    length = M.length;
    memcpy(digit, M.digit, maxlength*sizeof(int));
    this->checklength();

}
Mbigint Mbigint::operator+(Mbigint M)
{
    if (M.length==0)
        return (*this);
    if (length==0)
        return M;

    Mbigint T;
        T.length=max(length,M.length)+1;
        for (int i=1,temp=0;i<=T.length;i++)
            T.digit[i]=(temp=(temp/10000+digit[i]+M.digit[i]))%10000;
        T.checklength();
        return T;
}

Mbigint Mbigint::operator*(int M)
{
    Mbigint T;
    int temp=0, i;

    T.length = length+2;

    for(i=1; i<=T.length; i++)
        T.digit[i] = (temp=(temp/10000+digit[i]*M)) % 10000;
    T.checklength();
    return T;
}

Mbigint Mbigint::operator*(Mbigint M)
{
    int number, i, j, k, temp;
    Mbigint T;

    T.length = length + M.length;

    for(i=1; i<=length; i++) {
        number = digit[i];
        temp  = 0;

        for(j=1; j<=M.length; j++)
            T.digit[i+j-1] += number*M.digit[j];
        if(!(i%10) || i == length)
            for(j=1; j<=T.length; j++)
                T.digit[j] = (temp=(temp/10000)+T.digit[j]) % 10000;
    }
    T.checklength();
    return T;
}

Mbigint Mbigint::operator/(int M)
{
    int temp = 0, i;
    Mbigint T;

    T.length = length;
    for(i=T.length; i>=1; i--)
        T.digit[i] = (temp=(temp%M*10000 + digit[i])) / M;
    T.checklength();
    return T;
}

Mbigint Mbigint::operator%(int M)
{
    int temp=0;
    for(int i = length; i>=1; i--)
        temp = (temp*10000 + digit[i])% M;

    return temp;
}

// COMPARISON FUNCTION START HERE --------------------------------------------

bool Mbigint::operator<(Mbigint M)
{
    if(length != M.length)
        return length < M.length;
    for(int i = length; i>=1; i--)
        if(digit[i] != M.digit[i])
            return digit[i]<M.digit[i];
    return false;
}

bool Mbigint::operator<=(Mbigint M) {       return !(M<(*this));    }
bool Mbigint::operator>(Mbigint M)      {       return M<(*this);           }
bool Mbigint::operator>=(Mbigint M) {       return !((*this)<M);    }

bool Mbigint::operator==(Mbigint M) 
{       
    return (!((*this) < M) && (!((*this) > M)));    
}

bool Mbigint::operator!=(Mbigint M) 
{       
    return (((*this) < M) || ((*this) > M));    
}

// PRESENTATION FUNCTION START HERE --------------------------------------------

void show(Mbigint M)
{
    printf("%d", M.digit[M.length]);

    for(int i=M.length-1; i>=1; i--)
        printf("%04d", M.digit[i]);
}

Mbigint factorial(int num)
{
    Mbigint fact;
    fact = 1;

    for(int i=2; i<=num; i++) {
        //show(fact); cout << "\n";
        fact = fact * i;;
    }

    return fact;

}

int main()
{
    Mbigint fact;
    fact = 1;

    int input, i, sum=0, temp;

    while(cin >> input) {
        sum = 0;
        fact = factorial(input);

        for(i=1; i<=fact.length; i++) {
            temp = fact.digit[i];

            while(temp) {
                sum += (temp%10);
                temp /= 10;
            }
        }
        cout << sum;
        cout << "\n";
    }
  return 0;
}
Blog Comments powered by Disqus.

Next Post Previous Post