Spoj Problem Small Factorials : FCTRL2 Explanation & Solution

Problem:
Codechef: http://www.codechef.com/problems/FCTRL2/
Spoj: http://www.spoj.com/problems/FCTRL2/

In this Problem, we are required to find Factorials of numbers ranging from 1 to 100, but  Since an unsigned 64-bit Integer can store upto 19 decimal digits, where as 100! has 150+ digits, so we can’t use Int Data type.

The simplest data structure which can be used to store such results is an Array.   In the simplest form we can store 1-digit at every index of array.


How to store a two (or more) digit number  in an Array (one digit per index) ?

We need to store the input ‘n’ (1-100) into an array to find it’s Factorial To store a Number in an array, we can grab the digits from least significant position  (For Example 1456) one by one and put it into the array.                                                                                                                                                                                                                     For example:  To put 123 into an array (let say a[50]), we will grab the last digits one by one, final array would be given as  a[] = {3,2,1}  i.e. a[0]=3, a[1]=2, a[2]=1 & so on…

LOGIC used for this: Let n = 123 then  1). let rem = n%10 (this means remainder when n is divided by 102. a[index] = rem     3. n = n/10  (this removes the last digit from n, Now we are ready to grab the second last digit & so on)  Repeating this step iteratively, we can save n into an array.


 

How To Find the Factorial of the Number stored in array?

After we have put the input number (1-100) into an array, we have to now find its Factorial. To do that we have to multiply the number ‘n’ with (n-1), (n-2) … & so on …3.2.1 . Now we need to find an Algorithm for multiplying an Integer with a number stored into an array & we can use that algorithm for all multiplications.

Let us take an Example:    Let the n be 45, so we have to find it’s factorial 45! = 45x44x43x…..x37x…4x3x2x1. Now put the number 45 into a sufficiently large array (such as a[200]).  Now lets us multiply the array a[] = {5,4} with a number, let say 37

The array will be:
a[0] = 5
a[1] = 4
and the value of m will be 2 specifying that there are 2 digits in the array currently.

Now, to multiply this array with the value 37. We start off from the index 0 of the array to index 1. At every iteration, we calculate 37 * a[index]. We also maintain a temporary variable called temp which is initialized to 0. Now, at every step, we calculate x = a[index] * 37 + temp. The new value of a[index] will be x % 10 and the new value of temp will be temp / 10. We are simply carrying out multiplication the way it is carried out usually  (The Process is shown in Figure below). So, for the current situation, the iterations will be something like this.

Initialize temp = 0
Iteration 1 :
array = (5, 4)
temp = 0
index = 0, a[index] = 5
x = a[index] * 37 + temp = 5 * 37 + 0 = 185.
the new value of a[index] = 185 % 10 which is 5 and the new value of temp is 185 / 10 which is 18

Iteration 2 :
array : (5, 4)
temp = 18
index = 1, a[index] = 4
x = a[index] * 37 + temp = 4 * 37 + 18 = 166.
the new value of a[index] = 166 % 10 which is 6 and the new value of temp is 166 / 10 which is 16

We have finished 2 iterations and this is the value of ‘m‘, the array size at the moment. The required number of iterations is now over, but the value of temp is still greater than 0. This means that the current value of temp is to be incorporated into the array. For that, we keep appending the last digit of temp to the array and divide temp by 10 till temp becomes 0. So, we will get something like
Iteration 1 :
temp = 16 , array = (5, 6)
So, we add 16 % 10 to the array so that the array becomes (5, 6, 6) and we divide temp by 10 so that temp becomes 1. We update the value of ‘m’ to m + 1 that is m = 3
Iteration 2 :
temp = 1, array = (5, 6, 6)
Now, we add 1 % 10 to the array so the array becomes (5, 6, 6, 1) and we divide temp by 10 so that temp becomes 0. We update the value of ‘m’ to m + 1 that is m = 4

The value of temp is now 0 and our multiplication is now over. The final array we get is (5, 6, 6, 1)

Voila, we have the answer to 45 * 37 in our array with the Least significant digit in the 0th position. :)

For finding the factorial, we need to carry out this exact multiplication operation at every step as we loop from 1 to N. At the end of the Nth iteration, our array will contain
the answer and the value of m will be the number of digits in the answer. We can then just print the array from the Most significant digit to the least for the answer.

FCTRL2 Solution

Actual Multiplication of 37 x 45

Source Code Of Above Algorithm:

#include<iostream>
using namespace std;
int main() {
int t;
    cin>>t;
    while(t--) {
        int a[200],rem,i=0,n,m=0,flag;
        cin>>n;
        flag = n; 

        while(flag!=0)  {
            rem = flag%10;
            a[i] = rem;
            flag = flag/10;
            i++;  
             m++;
        } 

         int temp,x=0,index=0;
         for(i=2;i<n;i++)  {
             temp = 0;
             for(index=0;index<m;index++) {
                 x = a[index]*i + temp;
                 a[index] = x%10;
                 temp = x/10;
              }
 
              while(temp!=0) {
                  a[index] = temp % 10;
                  temp = temp/10;
                  index++;
                  m++;
               }
            }

            for(i=m-1;i>=0;i--) {cout<<a[i];}
                cout<<"\n";
            }
    return 0;
}

Thanks to this Tutorial at Codechef:  http://blog.codechef.com/2009/07/02/tutorial-for-small-factorials/

For Python Freaks, it’s a cakewalk.
10 lines of code!

def fact(a):
    factl = 1
    for i in range(1,a+1,1):  factl = factl*i
    return factl
def main():
    t = int(input())
    for i in range(t):
        n = int(input())
        print(fact(n))
if __name__ == "__main__":main()

 

What is SEO?

SEO Stands for “Search Engine Optimization”
As the name suggests SEO is the process of making improvements to your website so as to get maximum exposure in search engine results which is directly proportional to more number of visitors finding your website for the right reasons and going to your website and hence serving the purpose of your website.
In order to understand what SEO improvements needs to be done for better exposure in search engine results, Lets us first understand the working of a Search Engine:
A Search Engine works on a complex algorithm which searches for all the webpages related to the query entered by the user and arranges them in order of Relevance and Authority for best user experience.

 

iamit-SEO

 

Relevance
It refers to How relevant is your content to the search query. A search engine analyses all the webpages related to the query and ranks them after evaluating a number of factors such as how your content is written and Implemented on the code (Technical aspect). It is all about about making your website more relevant to the searchers through Content Optimization. More unique and relevant the webpage is to the community , More the traffic it will get.

Authority
Authority in SEO is the reputation of a website on the Internet. In  a Age where 2.7 billion people (roughly 40% of world’s Population) are using internet and every one is free to post anything on the web, is your website a trusted place on internet? this is what search engine evaluates and delivers to it’s users. The most common technique the search engine uses to measures the authority of a webpage is by determining what other websites think of you, that is by determining the links that are pointing to your website.
It’s not all about gaining links to your website, it’s the quality of links that makes the difference, for a better and effective SEO.
For e.g. A link from a .gov or .edu website have much greater value than a link from a 2 months old website.
Links from websites that has nothing to do with your niche(your website field/Stream/About) doesn’t have any impact on search engine exposure.

Search Engines have very smart algorithms to detect non-relevant or paid link, so Link Building is all about quality, not the quantity.

About

cropped-IMG_20130126_132731.jpg AMiT Kumar

I am a 20 Years old budding Engineer from New Delhi, India. Currently, I am Pursuing my B.Tech in Mathematics & Computing From Delhi Technological University (Formerly Delhi College Of Engineering). I love to get encountered with Latest Technology & Trends.

About iamit.in
It’s is my Personal Blog.

Contact: me [at] iamit [dot] in


 

 

 

Contact:

Your Name (required)

Your Email (required)

Subject

Your Message