# Frobenius coin problem variation

Suppose you are give $$n$$ currency notes from $$k$$ to $$k+n$$

i.e $$k, k+1,k+2.....k+n$$

Where $$k,n>0$$

It's asked the total number of denomination of money that can't be formed using any number of these notes.

My approch.

I can solve this when n=1. Ans is k*(k-1)/2 But How should i approach when n ≥1?

______
Source: https://www.codechef.com/JUNE19B/problems/CHFING

• Shouldn't it be from k to k+n-1? If it's from k to k+n you would have n+1 different notes. – Kruga Jun 25 '19 at 8:07
• @Kruga, good point. In my solution I assume OP meant "(n+1) currency notes". – ppgdev Jun 25 '19 at 20:25

## 1 Answer

Here is an answer

It is obvious that if $$k = 1$$ any amount of money can be formed.

If $$n \geqslant (k-1)$$ any amount of money greater or equal then $$k$$ can be formed. So the answer is

$$k-1$$

From now on we will only consider the case of

$$k > 1$$ and $$n < (k - 1)$$

Let

$$q = \lfloor \frac{(k - 1)}{n} \rfloor$$

Then the number of the amounts of money that cannot be formed is

$$(q + 1)(k - 1 - \frac{nq}{2})$$

Reasoning:

Any amount of money $$x$$ can be uniquely represented as

$$x = pk + r$$ where $$0 \leqslant r \leqslant (k - 1)$$

It is not difficult to observe that $$x$$ cannot be formed iff

$$np < r$$

If $$np \geqslant r$$ we can always start with $$p$$ bills of value $$k$$ and then keep increasing each of them until we reach $$x$$.

Now we can calculate the total by adding all amounts that cannot be formed for every value of $$p$$ from $$0$$ to $$q$$

$$p = 0:$$ $$(k-1)$$
$$p = 1:$$ $$(k-1) - n$$
$$p = 2:$$ $$(k-1) - 2n$$
$$...$$
$$p = q:$$ $$(k-1) - qn$$

Summing this sequence up for all values of $$p$$ gives us the formula:

$$(q + 1)(k - 1 - \frac{nq}{2})$$