IOPCA - Fun with flooring factorial

How was the question supposed to be solved? Can someone provide a hint?

1 Like

You basically have to perform modulo multiplication(with m) for all numbers between [1,N], where m=2b.
For example n=5 , b=7 hence m=2
So you find (n! % m) = 120%14=8 now since 8>= b, answer is odd.
Why does it work?
7x2=14             14x1=14

7x14=98            14x7=98
7x16=112            14x8=112
7x18=126             14x9=126

Now 120 lies between 112(14x8) and 126(14x9) which means in 7s table it falls between (7x16) and (7x18)
Since you know the remainder of 120%14=8
112 % 14 … 126 % 14 = 0,1,2,3,4,5,6,7,8,9,10,11,12,13,0 (14s table)
112 % 7 … 119 % 7 … 126 % 7 =0,1,2,3,4,5,6,0,1,2,3,4,5,6,0 (7s table)
if remainder is <7 , 16 would be your quotient but here remainder=8 which is >=7 , hence quotient would be 17.

Hence this method is independent of finding the quotient!!! You just find the remainder with (2*b) and judge.


In the solution above given by @rohansuri which is perfect the case of 0 is needed to be separately handled as 0 Factorial is 1.

@rohansuri: nice explanation bro.

Is this property has any name or any theorem ??

It is just normal Fast modulo multiplication but the difference is that the modulus is 2b instead of a prime number. This is just simple maths.Since you want to know even or odd ,When the number is divisible by 2b ,then the quotient ,when divided by b, is guaranteed to be even. All that is left is to examine the remainder obtained. If it greater than b, then it is odd because you could have divided it by b one more time otherwise it is even