Problem link
Difficulty
SIMPLE
Pre-requisites
base representation
Problem
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.
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(logK(N)) because this is maximum value of d as defined above.
Tester’s solution: Will be added Later