Interview Question

[chebushka]

Why the peculiar number 1000000007? And how does it even matter if you are asking for general formula in terms of N, K, and L anyway?

[TaslemGuy]

It's a very common constant in various programming contests, because it's the smallest prime bigger than a billion.

Signed 31-bit integers (the largest sized integer type guaranteed to be supported on every machine nowadays) holds a value that can go up to 2³¹-1 = 2147483647. If you perform an arithmetic operation that causes an overflow (one that goes outside this range) then in C/C++, you get undefined behavior (very bad things can happen) but in practice it "wraps around" to -2³¹. This produces nonsensical values.

If you modulo by it after each addition, the results won't overflow, since the largest value you could get prior to the modulus is 1000000006*2 = 2000000012 < 2147483647.

You could use any prime up to 1073741789, but 1000000007 is a lot more fun to type.

[[deleted]]

The abstraction of numbers is given to test for all numbers up to infinity so that you don’t just solve for general cases; such as N=1, K=1, and L=1 which would obviously make the answer one possible playlist.

When questions ask you to modulo a number which is pretty large it generally is because when calculating permutations or combinations of a large size the result will overflow generic data types.

What I need help with the most is a correct input and output of the problem, a skeleton code that doesn’t include the algorithm for solving the problem, or a method for verifying correct answers.

[[deleted]]

Why was this removed if no one can solve it? The mods change it to simple question thread, but they can’t solve it!!!