10323 - Factorial! You Must be Kidding!!!

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10323 - Factorial! You Must be Kidding!!!

Post by brianfry713 » Sat Dec 08, 2012 5:06 am

Check input and AC output for thousands of problems on uDebug!

Sleey
New poster
Posts: 1
Joined: Sun Sep 06, 2015 3:56 pm

Re: 10323 - Factorial! You Must be Kidding!!!

Post by Sleey » Sun Sep 06, 2015 3:59 pm

plamplam wrote:Lol this problem is indeed mathematically wrong. The factorial of negative integers are undefined according to the gamma function. The definition of the factorial function is:
(An example of a piece-wise defined function)
0! = 1
n! = n*(n-1)! for n > 0
I found in some previous posts that people said the factorial of 0 is 0....so the factorial of - 1 should be 0!/ 0. I am just writing this post for clarification.

First of all, note that 0! is not equal to 0. 0! = 1 (Check it out with your calculator :wink: ). The reason for this is demonstrated as below:
5! = 120
4! = 5! / 5
3! = 4! / 4
2! = 3! / 3
1! = 2! / 2
So, 0! = 1! / 1

An example of backtracking.

Another example:
nCk is the number of combinations possible you can choose k objects from a given set set of n objects.
By definition:
nCk = n! / (k! * (n - k)!)
So 0! = 1 neatly fits what we expect nC0 and nCn to be.

Also note that, before I give you the judge's logic(which is of course incorrect) for this problem, you must first understand the true logic. Anything divided by 0, Say 4 / 0 is NOT inifinity, rather it is not defined. That is why mathematicians refer to numbers that are divided by 0 as "undefined". (There is a special term for this called "indeterminate", search the web for more info) Some people tend to think of them as being infinite, but this isn't exactly true. There simply is no answer.

So We know that 0! = 1 now. We can use the same backtracking method to find -1!. Note again, that it is not possible to find factorials of negative numbers. By definition, -1! = 0! / 0
So, -1! = 1 / 0 = indeterminate
Again, -2! = -1! / -1 = indeterminate too(As -1! doesn't exist on the numerator, it follows that -2! also doesn't exist).

However the judge says that:
0! = 1 (True so this is an underflow)
-1! = 1 / 0 = +infinity = overflow (Wrong logic)
-2! = -1! / -1 = +infinity / -1 = -infinity = underflow(Again wrong logic!)
-3! = -2! / -2 = -infinity / -2 = + infinity = overflow......

I hope you understand now, why you need to check if n <= 0 then if (n % 2 == 0) = Underflow! and if (n % 2 != 0) = Overflow!
Note that this is mathematically and logically incorrect. This problem is just simply wrong(Wrong just because of the input contains negative numbers, if the dataset consisted of only positive numbers then the problem would be just fine)....its solution is wrong too. I just demonstrated the false logic which the judge uses.
Best Regards :) :wink:
Make account just for say thank you to you
I already try and googling about factorial what make me wrong until i see your post
but why this problem still here or not fixed?

Post Reply

Return to “Volume 103 (10300-10399)”