1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Kruga Jun 25 '19 at 8:07
  • $\begingroup$ @Kruga, good point. In my solution I assume OP meant "(n+1) currency notes". $\endgroup$ – ppgdev Jun 25 '19 at 20:25
2
$\begingroup$

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})$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.