Multifactorial | Topcoder Archive

Problem Statement

A multifactorial of a number is a generalization of the factorial function. The k-multifactorial of n is denoted by fac_k(n). The k-multifactorial of n is the product of every positive number of the form n - X*k, where X is a non-negative integer. For example, the 3-multifactorial of 14 is 14*11*8*5*2 = 12320, and the 4-multifactorial of 5 is 5*1 = 5.

A formal definition of multifactorial is:

fac_k(n) = n if k >= n
fac_k(n) = n*fac_k(n-k) if k < n

You will be given n and k and have to return the value of fac_k(n) as a String with no leading zeroes (this value is always a positive integer). If fac_k(n) is strictly greater than 1000000000000000000 (10¹⁸), return "overflow" (quotes for clarity) instead.

Definition

Class:: Multifactorial
Method:: calcMultiFact
Parameters:: int, int
Returns:: String
Method signature:: String calcMultiFact(int n, int k)
(be sure your method is public)

Notes

1000000000000000000 (1018) fits in a long.

Constraints

n and k will each be between 1 and 2000000000 (2*109), inclusive.

Examples

```
14
```
```
3
```
```
Returns: "12320"
```
The first example in the problem statement.
```
5
```
```
4
```
```
Returns: "5"
```
The second example in the problem statement.
```
1000
```
```
2
```
```
Returns: "overflow"
```
Way too big!

2000000000

1900000000

Returns: "200000000000000000"

```
1000
```
```
256
```
```
Returns: "84232704000"
```
```
2000000000
```
```
1
```
```
Returns: "overflow"
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.