IITK2P01 - Editorial

Problem link





base representation


A monetary system of a country has coins of following values
K0 , K1 , K2 , K3 , … (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.


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(logK(N)) because this is maximum value of d as defined above.

Tester’s solution: Will be added Later