n! % k when n,k is integer type

Asked Oct 29 '18 at 18:17

Active Oct 29 '18 at 18:17

Viewed 56 times

I`m trying to implement a java code which n,k is integer (can not be long type) which calculate the result of n! %k for any n,k. for ex, for n=18 and k=71 I want to get 56 and not -18.

I`m thinking that this algorithm should works through modules math, since the result is built by n=k*m+r (r is the division). Any ideas how to implement this algorithm with integer type?

Below is my code and is working but not for any n,k:

    int n = scanner.nextInt();
    int k = scanner.nextInt();
    int result = 1;
    //n!
    while (n!=0){
        result = result * n;
        n=n-1;
    }
    System.out.println(result % k);

asked Oct 29 '18 at 18:17

John D

try `result = result * n % k;` so it doesn't overflow. – Peter Lawrey Oct 29 '18 at 18:18
See [How to avoid overflow in modular multiplication?](https://www.geeksforgeeks.org/how-to-avoid-overflow-in-modular-multiplication/) – Andreas Oct 29 '18 at 18:21
1

With early reduction, if `k` can be greater than the square root of the maximum integer, the product may still accidentally wrap modulo 2^32 in addition to wrapping modulo `k` – harold Oct 29 '18 at 18:24
Using `long result` is a safer option for large values of `n`. – Peter Lawrey Oct 29 '18 at 18:27
Also if `n >= k` the answer is 0. – Peter Lawrey Oct 29 '18 at 18:28
1

@PeterLawrey if n>=k so n! has k as a divisor then the answer for this is correct. right? – John D Oct 29 '18 at 18:40
@JohnD yes, indeed. – Peter Lawrey Oct 29 '18 at 19:13

n! % k when n,k is integer type

0 Answers0