CodeChef Tutorial: Your First Non-Trivial Problem

Hello people…. Today, we are going to make our first non-trivial program submission, and I am going to guide you through reading the problem statement through making a successful submission. I will also be touching the issue of “time limit” and “source limit” in this tutorial. However, I won’t be revealing too much in terms of code, so you will still have to do the hard work!

I’ll be using the Small Factorials problem as the program driving this tutorial.

Here is the problem statement:

You are asked to calculate factorials of some small positive integers.

Input:
An integer t, 1<=t<=100, denoting the number of test cases, followed by t lines, each containing a single integer n, 1<=n<=100.

Output:
For each integer n given at input, display a line with the value of n!

Example
Sample input:
4
1
2
5
3

Sample output:
1
2
120
6

Time limit: 1s

Source limit:2000B

The problem statement is fairly simple. We all recall that the factorial of a natural number n is the product of all numbers from 1 through n. Recursively, we can define the factorial of a natural number n as the product of n and factorial of (n-1). So, factorial(n) = n X factorial(n-1) and factorial(1) = 1.

You may ask why we haven’t considered factorial(0) = 1? Well, if you read the problem statement carefully, the least number that you will ever be asked to compute the factorial for is 1, so we don’t bother about any number less than 1.

As a first attempt, we would try and think that this program can be trivially coded up using integers or even long long integers, but a quick glance at the upper bound on the input number suggests otherwise. How do you figure out the number of digits in the factorial of 100? We can surely try and find a pessimistic approximation. Do you remember that the number of digits in the product x*y is either digits_in(x) + digits_in(y) or digits_in(x) + digits_in(y) – 1. So let’s try and find out the number of digits for 100!.

Pessimistically, it must be:

digits_in(100) + digits_in(99!), which is:

3 + digits_in(99) + digits_in(98!)

…. and so on….

which is 3+2*90+1*9 = 192

so, in the worst case, we have 192 digits in the result.

This itself should prompt us to not use integers because it will overflow even the biggest integral data type(64-bit) that we have.

The next thing we may think of is to use floating point numbers, but that too can be ignored for the same reasons.

Now that we find ourselves in a fix, we will try and resort to creating our own big integer class. This is where selection of programming language comes into play. Usually, C/C++ is the programming language of choice because of it’s speed and wide adoption. However, now is a good time to look at languages like Java, Python, Caml, etc…. which have built-in support for indefinitely long integral values. So, if you know any of those languages, this problem should be a breeze to solve! And CodeChef allows you to choose one of 30+ different programming languages for coding your solution in!

Once you have coded up a solution in your language of choice and submit it, you find that it says “Wrong Answer”. You wonder “How could that happen” and try to figure out where to start debugging. You enter integers 4, 5, 6 and get the answers as 24, 120, and 720 respectively which are correct. Then you enter the number 50 and you get a really huge number. However, you wonder to yourself “How do I know if this is the correct value of 50!?”. You think for a while and then let it go. Here is where you should think some more.

As a first level of sanity checking, the output should have at least 5 zeros at the end because 50! involves multiplying 10, 20, 30, 40 and 50. If not, you can start debugging. However, even better would be if you knew the exact number of zeros to expect at the end of the output.

Here is how you can find that out. You need to know that you can get a zero at the end of the product of 2 numbers if and only if 10 is a factor of the number. This is possible only if 2 and 5 both are factors of the product.

You can write a simple program to count the number of times a factor of 5 or 2 occurs in all the numbers from 1 to 50, and the number of zeros to expect is the least of the two values. This should validate(to a great extent) your solution’s output.(This co-incidentally is the solution to another problem in the easy set).

What does the “Time limit” mean? It means that the program that you write should be able to compute the factorial of 100 numbers, each of which are <=100 in 1 second.

If I was solving this problem and I saw the constraints mentioned, I would just pre-compute all the values for factorials of numbers from 1 to 100 and store it as strings in my program’s code, and the display the required string depending upon the input. However, to thwart lazy coders like me, the problem setter has set a Code size limit which is “Source limit”. So your program’s source code must be at most 2000 Bytes.

We have already computed the largest result as having at most 192 digits. So, on the average, you can expect each result as having at most 96 digits. If I wanted to store all the values, I would need at least 96*100 bytes of storage, which is 9600 bytes, which exceeds the source limit. This makes it fairly impossible for me to hard-code the answers in the program.

Get Started With Coding – Tutorial For Find Remainder…

Hey! If you are a beginner in the vast world of programming, then you are at the right place. In this CodeChef tutorial blog,...
ganga4518

Get Started With Coding – Tutorial For a Simple…

New to the programming world, yet intrigued? Let’s get you started with the CodeChef journey with a very basic “Add Two Numbers” problem. So...
ganga4518

Watch The Inspiring Story Of Malvika Raj Joshi Who…

Do you remember the person who got into MIT without the conventional schooling style you are used to? Would it come as another big...

29 Replies to “CodeChef Tutorial: Your First Non-Trivial Problem”

1. Alok says:

You are right about all this but what about someone who has done it in C++ only. Since C++ won’t allow you to go beyond a certain value, you can’t help it. Many use 32 bit system so max value one can use is around 2700000000. Can you suggest something about this ?

2. Alok says:

You are right about all this but what about someone who has done it in C++ only. Since C++ won’t allow you to go beyond a certain value, you can’t help it. Many use 32 bit system so max value one can use is around 2700000000. Can you suggest something about this ?

3. Prakhar says:

Man Exactly. I am getting freaky like anything while doing online programming. Similar thing happens to me while doing programming at spoj.pl and projecteuler.com

Everytime I try write a code in C++ using simple turbo, it works fine, and gives the required result. But that program fails when a large input is given.

HELP ME! I AM A C++ CODER…

4. Prakhar says:

Man Exactly. I am getting freaky like anything while doing online programming. Similar thing happens to me while doing programming at spoj.pl and projecteuler.com

Everytime I try write a code in C++ using simple turbo, it works fine, and gives the required result. But that program fails when a large input is given.

HELP ME! I AM A C++ CODER…

5. Ashutosh Agarwal says:

ou are right about all this but what about someone who has done it in C++ only. Since C++ won’t allow you to go beyond a certain value, you can’t help it. Many use 32 bit system so max value one can use is around 2700000000. Can you suggest something about this ?

6. Ashutosh Agarwal says:

ou are right about all this but what about someone who has done it in C++ only. Since C++ won’t allow you to go beyond a certain value, you can’t help it. Many use 32 bit system so max value one can use is around 2700000000. Can you suggest something about this ?

7. Dhruv says:

Hello Ashutosh,
You’ll just have to implement your own large integer handling class if you want to do it in C++.

HTH.

8. Dhruv says:

Hello Ashutosh,
You’ll just have to implement your own large integer handling class if you want to do it in C++.

HTH.

9. rahul says:

hi ashutosh/alok,
you have to define your own class to handle the bigger nos.
try this i think it’ll surely help u out.

10. rahul says:

hi ashutosh/alok,
you have to define your own class to handle the bigger nos.
try this i think it’ll surely help u out.

11. Ashutosh says:

I have implemented this algorithm to find the no. of zeros in the factorial of a no. by simply finding the no. of factors of 5 and 2 and then printing the min of them. But the answer is coming out to be wrong. As in 60 there are 14 zeros and this algorithm gives the output 12. what should i do ?

12. Ashutosh says:

I have implemented this algorithm to find the no. of zeros in the factorial of a no. by simply finding the no. of factors of 5 and 2 and then printing the min of them. But the answer is coming out to be wrong. As in 60 there are 14 zeros and this algorithm gives the output 12. what should i do ?

13. Dhruv says:

You should note that the number of factors of 5 in numbers from 1 to 60 is: 12 + 2 (the 2 coming from 25 and 50, which both have 5 as a factor 2 times).

14. Dhruv says:

You should note that the number of factors of 5 in numbers from 1 to 60 is: 12 + 2 (the 2 coming from 25 and 50, which both have 5 as a factor 2 times).

15. It would be much easier, if instead of stdin and stdout, you would allow the programs to read through file and then write to a file. This thing bugs me off. I want to know if
(1) We need to take one input line at a time, process it and show the solution? OR
(2) We need to accept all input lines at one go, and then process and show the results in one go

16. It would be much easier, if instead of stdin and stdout, you would allow the programs to read through file and then write to a file. This thing bugs me off. I want to know if
(1) We need to take one input line at a time, process it and show the solution? OR
(2) We need to accept all input lines at one go, and then process and show the results in one go

@Pranav:
Do it either way. All you need to do is make sure your output is FORMATTED properly. It doesn’t matter if the output comes inbetween your program while running.

@Pranav:
Do it either way. All you need to do is make sure your output is FORMATTED properly. It doesn’t matter if the output comes inbetween your program while running.

19. mandar says:

I am getting compiling error..
I code in Java. i exactly wanted to know what is the difference between java and JAR.
More over i use netbeans as my IDE and hence want to know what should I do to rectify and correct the Compilation error as the program works fine at my home PC.
-Thank u.

20. mandar says:

I am getting compiling error..
I code in Java. i exactly wanted to know what is the difference between java and JAR.
More over i use netbeans as my IDE and hence want to know what should I do to rectify and correct the Compilation error as the program works fine at my home PC.
-Thank u.

21. CodeManic says:

Hi,
I coded using Perl.Everything went well but i got wrong answer. I dont know were i went wrong. Can anyone help me

22. CodeManic says:

Hi,
I coded using Perl.Everything went well but i got wrong answer. I dont know were i went wrong. Can anyone help me

23. sukant says:

@CodeManic…where exactly you got stuck? do let us know then we’ll try to fix the bug and get the correct answer. thanks.

24. sukant says:

@CodeManic…where exactly you got stuck? do let us know then we’ll try to fix the bug and get the correct answer. thanks.

25. Ivneet says:

My prgogram is running properly in turbo c. what do i do?

26. Ivneet says:

My prgogram is running properly in turbo c. what do i do?