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 number  in an Array?

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/

You Must stand tall, No Matter What!

4/1/2014
This is my first post this year, so first of all Happy New Year Everyone! This post is result of some of my recent experiences of the taste of life!
There is a popular saying in English, “Big birds of storm” , whenever there is intense storm, the birds with smaller wings are caught up in it, & the birds with larger wings (large birds) fly firm & higher.
This is pretty analogue to life also! when the situation is good & fair it is usual to be happy & jolly, but when it’s not then survival depends on our wings!, i.e. our perspective towards the situation & that’s what tests us on the Litmus test of Life.

…. to be continued.

Raj Kapoor The legend

Raj Kapoor The legend
 
A Random article about one of the best Actors of all time.
 
We all know about the famous Actor, Director, Producer, and the ultimate showman of Indian cinema i.e. “Raj Kapoor” The man with an extraordinary but a simple philosophy. His films were not only made to extract profit but to teach humanity, brotherhood and of course the ideal art of living. The music in his films had a different rhythm whose lyrics had a soulful meaning which carried the aroma of mankind.
In contrast to today’s movies and music they are intentionally made to earn huge profit and fame by destroying moral and ethical values and are solely inspired from the west. Many a times I wonder why to look at west, when the sun rises from east! India, the country of its rich culture and heritage is losing its identity.

 

Raj Kapoor was not only renowned in India, but also in other parts of the globe, especially Russia. His movie “Mera naam Joker” had a great success in Russia though it didn’t run initially in India. In this movie Raj played the role of a joker who went through a number of tragedic hard times, but still doesn’t fails to depict the greatness of a joker who always laughs to make others laugh irrespective of joy and sorrow. He is, who sacrifices everything but never complains.    
 
To be conitnued..

Simple Is Extraordinary!

 “The difference between being great and being successful”

Many a times while reading the biography of some great men we may wonder why we aren’t like them or what differentiates them from others and what should may be done to become like them. We may subconsciously arrive at the conclusion that, they were born with some extraordinary skills which are horned later in there life and eventually they are extraordinary. Though this is off course not true since once greatness is not a matter of chance or luck, it’s a matter of attitude which is common in all great men. 

Simplicity though sounds to be very simple but makes the difference between ordinary and extraordinary as we can aspire to touch the sky only when we are down to earth. Although, being simple alone doesn’t certify for one’s greatness but measure’s it to a great extent. Being simple doesn’t only mean wearing simple clothes or putting simple boots but keeping your attitude simple, and your character to be an open book. If we talk of Mahatma Gandhi the ‘great’ he also had a simple philosophy of “Simple living and high thinking”, not only mahatma Gandhi, all great men had these feature common hence there is no doubt that greatness resides in simplicity. So to become great be simple, and to being simple just forget about those scars and pimples on your face, forget thinking about what people will say about you, forget about all mundane things, and hence you are simple!

It is indeed ridiculous to know that, nowadays, many stars and not so famous personalities are getting involved in cheap and mundane activities, just to gain some name and fame, but being renowned all over the globe or over the nation doesn’t mean to be great; One is great by his activity not by his publicity. To be great, it’s not necessary to be called as “great” by others; instead we must listen “great” from our soul, to be truly great. 

 

Be Simple and yes, you are extraordinary! 

Year of Article: 2011 

“Self”-The Best Friend

24 July, 2012
New Delhi

 


Why to look for someone else during calamity, when we are so self capable. The situation may not be in our favor every time but the happiness is only enjoyed well when we have gone through sorrow. Autumn wouldn’t be so charming without experiencing the winter. Thinking of the solution of a problem worth much better than cursing the destiny for what we have got.

 
We always try to look for someone to give hands when we are struck inside the dig, and then we fail to find anyone and then realize we are alone in this crowded World. Why to look for someone else to give a push, when we alone have to climb the Everest.
 
We may think ourselves alone in this cruel world but the Almighty is always taking the account of every road we are trudging, he is always behind us to show the right path, but it’s all up to us when we identify it. It’s always important to learn from life, since learning from life is what the life is! Nature is always going to reward us for the right and vice-versa for the wrong.
 
We came alone and yes we have to leave alone and in the journey of life our best friend is self whom we can trust for sure.

 

It was well said by Charlie Chaplin-“My best friend is mirror, because it never laughs when I  cry.”

Law Of “KARMA”: A Bank Transaction

I wrote this article in the summer of 2011, those days were one of the toughest days of my life!

 

karma

What is “Karma”? There are infinite answers to this question by infinite philosophies but what the Karma actually is? Karma is the ultimate law of nature whose mechanism is very much similar to that of bank transaction. When we are born an account on our name is automatically opened in the ‘bank of karma’. At that time we have nil balance i.e. our destiny is not defined. As we grow older our deeds and actions pay to our account and makes our destiny.
Our good deeds are debited, and as a bank account when we deposit something we get interest along with the deposited amount, we get more than what we give by doing good deeds. The converse is true as well, we have  to pay more than what we take by doing bad deeds same as in bank’s mechanism we have to pay abundant interest to the bank for the loan we take, hence bad deeds are credited as well.

The mechanism mentioned above truly describes the Law of Karma if the concept of rebirth is not taken into account. The question which is of prime importance when the concept of rebirth is considered is that why some are born more blessed than others? One is born in a palace and other in a slum. This may be answered by considering the actions of last birth, which are also counted while landing on earth i.e. the sum total of debit and credit of the account of last birth. It means we may not get the fresh account every birth, one single account is issued to the soul, no matter the number of births one may take his account is always active!
The Theories on Karma and rebirth are mere postulates, nothing can said with due sureity. It’s our experiences which tells about the validity of a particular theory.

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
IAMIT is my Personal Blog.


 

 

 

Contact:

Your Name (required)

Your Email (required)

Subject

Your Message

The Joy Of Being Good!


An Article On Self Improvement 
There are millions of articles and Books On self Improvement and yet this one!
I am no way following the footprints of those spirutual gurus, but this article is a simple approach on the idea of being good. Read and Implement if you find anything useful.
(I wrote this in the summer of 2011)


 The Joy Of Being Good!

What it takes to become bad? Simply nothing, but it takes a lot of character and goodness to become good. The Joy of being good is equally larger as the pain of being bad, but still most of us trudge the second path. Why? It is due to the myopia of short term gain, thesecond path appears to be the bed of roses to many of us. That’s off course an illusion by which we are allured and get easily trapped into the bait. Though the second path promises short term pleasures and quick fixes, but it can never guarantee you the lifetime pleasure. 

By choosing the second path we may be overwhelmed by its initial offerings but we have to pay the price for it in future. Hence the second path which appears to be the easier one is actually the tougher one! Conversely the first path may not promise for the short term pleasures but guarantees you sure shot high on self esteem, confidence and also the Peace of the soul. Then why not choose the first path than to become the slave of our own deeds in the second path? Change is always undesirable and human being particularly tends to resist change. 
Though getting on to the first path is not too difficult, but it’s a matter of will and determination to get on the right track. It’s rightly said in bhagwad gita “Chanchala hi mana, abhyase hi vasham”: means mind is easily enchanted by the lure of the negative, but can be controlled by Practice. One has to change the default programming of his mind to explore the Joy of being good. Tough, but not the toughest! And hence the Joy is extremely larger!!