Extra Long Factorials Hackerrank problem solution

Extra Long Factorials Hackerrank

You are given an integer N. Print the factorial of this number.
N!=N X (N-1) X (N-2) X ……3 X 2 X 1
Input
Input consists of a single integer N, where 1<=N<=100.Output Print the factorial of N.Example For an input of 25, you would print 15511210043330985984000000.Note: Factorials of N>20 can’t be stored even in a 64-bit long long variable. Big integers must be used for such calculations. Languages like Java, Python, Ruby etc. can handle big integers, but we need to write additional code in C/C++ to handle huge values.

We recommend solving this challenge using BigIntegers.

Solution

Factorial of a number can be calculated by simply multiplying values N * N-1 * N-2 * … * 2 * 1. But for N > 20, this value becomes quite large and doesn’t fit even in a 64 bit long long variable. Languages like Java, Python, Ruby etc. provide support for Big Integers. We can solve this problem easily in these languages by using the Big integer libraries provided.
But in C / C++, we need to write additional code to handle big integer values. In the simplest form, we can store the factorials in an array with one digit at each index of the array.
For example : To store 245 in the array,
a[2]=2
a[1]=4
a[0]=5
To multiply a number say k to this value, we start off from the index 0 of the array. At every iteration, we calculate k * a[index]. We also maintain a carry from the previous index which is initialized to 0. Now, at every step, we calculate product = a[index] * k + temp. The new value of a[index] will be product % 10 and the new value of carry will be product/10. We propogate this carry to higher order digits.
Example:

arr[1]=3
arr[0]=6

We need to multiply arr by 5. We first multiply 6 by 5.
6*5=30, 30 % 10 = 0, 30/10=3;
arr[0]=0;
carry=3.

We then multiply arr[1] by 5.
prod = arr[1]*5 + carry
prod = 3*5+3=18
arr[1] = prod%10 = 8
carry= prod/10 = 1

Propogating the carry
arr[2]=1

arr[2]=1, arr[1]=8, arr[0]=0
To calculate the factorial of a number, we need to multiply N * N-1 * … * 2 * 1.
100! contains less than 200 digits so we can keep the size of the array to be 200.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int mult(int size,int res[],int x)
    {
    int carry=0,prod;
    for(int j=0;j<size;j++)
        {
        prod=res[j]*x+carry;
        res[j]=prod%10;
        carry=prod/10;
    }
    while(carry)
        {
        res[size]=carry%10;
        carry=carry/10;
        size++;
    }
    return size;
}
void fact(int n)
    {
    int i,size;
    int res[200];
    res[0]=1;
    size=1;
    for(i=2;i<=n;i++)
        {
        size=mult(size,res,i);
    }
    for(i=size-1;i>=0;i--)
        printf("%d",res[i]);
    
}
int main() {
int n;
    scanf("%d",&n);
    fact(n);
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    return 0;
}
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main(){ 
    int i,num,a[200],j,size,p,t,c;
cin>>num;
a[0]=1;
size=1;
for(i=2;i<=num;i++)
    {
        p=size;c=0;
        for(j=0;j<size;j++)
            {
                t=a[j]*i+c;
                c=t/10;
                a[j]=t%10;
        }
    while(c)
        {
            a[j]=c%10;
            size++;
        j++;
            c=c/10;
    }
}
for(i=size-1;i>=0;i--)
    {
    cout<<a[i];
}
          return 0; 
          }
from math import factorial as f
print f(input())
#include <vector>
#include <iostream>

using namespace std;

int main() {
    int val;
    int carry = 0;
    cin >> val;
    vector <int> arr(200, 0);
    arr[0] = 1; //Initial product = 1

    int k = 0; //Current size of the number stored in arr

    for(int i = 1; i <= val; i++) {
        for(int j = 0;j <= k; j++) {
            arr[j] = arr[j] * i + carry;
            carry = arr[j] / 10;
            arr[j] = arr[j] % 10;
        }
        while(carry) { //Propogate the remaining carry to higher order digits
            k++;
            arr[k] = carry % 10;
            carry /= 10;
        }   
    }
    for(int i = k; i >= 0; i--) {
        cout << arr[i];
    }
    cout << endl;
    return 0;
}

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.