### Problem link

### Difficulty

SIMPLE

### Pre-requisites

base representation

### Problem

A monetary system of a country has coins of following values

K^{0} , K^{1} , K^{2} , K^{3} , … (till infinity)

Also we have K coins of each type.

Find out minimum number of coins needed to make sum of their values equal to N.

### Solution

**Observation 1**

Represent N in base K. Let us say its representation is A[1], A[2], , A[d] where d denotes number of digits in base K notation of N.

**Observation 2**

Each A[i] < K because it is base K representation of N.

**Final Solution**

Now you can pick A[i] coins of type K^i and generate N. So total number of coins needed will be A[1] + … + A[d].

**Small Homework**

Prove that the above greedy solution is optimal.

**A small pitfall**

If K = 1, then you have to pick all the coins to make N. Now in that case if you try creating base representation of N in base 1, It is not possible to do so. Depending on your

code, it might lead to TLE.

**Time Complexity**

O(log_{K}(N)) because this is maximum value of d as defined above.

**Tester’s solution**: Will be added Later