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=2b=14.
So you find (n! % m) = 120%14=8 now since 8>= b, answer is odd.
Why does it work?
7x1=7
7x2=14 14x1=14
7x3=21
…
7x14=98 14x7=98
7x15=105
7x16=112 14x8=112
7x17=119
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.
7 Likes
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.
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