## Interview Question

Interview Menlo Park, CA

## You are given an integer N and an integer M. You are

supposed to write a method void findBestCoinsThatMinimizeAverage(int N, int M) that prints the best collection of N coins that minimize the average number of minimum coins needed to generate values from 1 to M. So, if M = 100, and N = 4, then if we use the set {1, 5, 10, 25} to generate each value from 1 to 100, so that for each value the number of coins are minimized, i.e. 1 = 1 (1 coin), 2 = 1 + 1 (2 coins),..., 6 = 1 + 5 (2 coins), ..., 24 = 5 + 5 + 5 + 5 + 1 + 1 + 1 + 1 (8 coins), and we take the average of these coins, we would see that the average comes out to ~5.7. But if we instead use {1, 5, 18, 25}, the average would come out to be 3.7. We are to find that set of N coins, and print them, that produce the minimum average.

## Interview Answer

8 Answers

We need some way to narrow down the subsets of N that we consider. Perhaps we could start by enumerating the subsets of N lexicographically, and then performing a binary search on the array of subsets to help us choose? Just a thought, not very developed yet.

Why is 24 = 5 + 5 + 5 + 5 + 1 + 1 + 1 + 1? Should it not be 10+10+1+1+1+1?

I doubt this question really was a Facebook interview question (although I am not a Facebook employee nor do I have any connection with Facebook). Anyway, here is a research paper precisely on this problem: http://www.cs.uwaterloo.ca/~shallit/Papers/change2.pdf It is written by a well known researcher in algorithms and he says on page 6 (problem 5) that this problem is hard and that he wasn't able to find a polynomial time algorithm for it. So the best way to do do it is to enumerate all possible denomination subsets, and then for each value and each denomination system, compute what the minimum number of coins for that value is using the well known dynamic programming approach. And to the previous commenter (A): you are absolutely right.

Just based on the reading of the problem it sounds very much like a variation of the Knapsack problem (optimization) which is NP Hard. The problem grows exponentially harder as N grows. Except for small values of N, algos for computation are not likely to return for a long time.

very slow... need to reduce generating coins sets... public class Solution { private static ArrayList<int[]> coins = new ArrayList<int[]>(); private static void generatesets(int[] n, int k, int M, int N) { if (k == N) { coins.add(n.clone()); return; } for (int i=n[k-1]+1; i<=M-N+k+1; i++) { n[k] = i; generatesets(n, k+1, M, N); } } private static int countto(int[]n, int from, int M) { int res = Integer.MAX_VALUE; int k = 0; while (k*n[from] <= M) { if ((from + 1 < n.length) && n[from+1] <= M - k*n[from]) { int cto = countto(n, from+1, M - k*n[from]); if (cto != Integer.MAX_VALUE) res = Math.min(res, k + cto); } if (k*n[from] == M) res = Math.min(res, k); k++; } return res; } public static void findBestCoinsThatMinimizeAverage(int N, int M) { int[] n = new int[N]; n[0] = 1; generatesets(n, 1, M, N); float minc = Integer.MAX_VALUE; int[] res = null; for (int[] coinset : coins) { float averagecnt = 0; for (int j=1; j<=M; j++) { int cto = countto(coinset, 0, j); averagecnt = (averagecnt * (j - 1) + cto) / j; } if (minc > averagecnt) { minc = averagecnt; res = coinset; } } System.out.println(Arrays.toString(res)); } }

Not sure of the proof of correctness; just an iterative algo trying to implement pattern; more test-cases will be helpful. import java.io.IOException; import java.util.Scanner; import java.util.Set; import java.util.TreeSet; public class BestCoins { public static void main(String[] args) throws IOException { final Scanner in = new Scanner(System.in); while (true) { System.out.println("Enter total number of coins : N : "); int n = in.nextInt(); System.out.println("Enter max coin value : M : "); int m = in.nextInt(); Set<Integer> coins = new TreeSet<Integer>(); findBestCoinsThatMinimizeAverage(m, n, coins, true); System.out.println("Best coin set is " + coins); } } private static void findBestCoinsThatMinimizeAverage(int m, int n, Set<Integer> coins, boolean minimize) throws IOException { System.out.println(m + " " + coins + " " + minimize); // new BufferedReader(new InputStreamReader(System.in)).readLine(); if (m <= 1) { coins.add(1); return ; } int coin = minimize? m/n : m-m/n; if (coin == 0) { coin = 1; } coins.add(coin); if (coin == 1) { coins.add(m-1); return; } int remainingM = minimize? coin-1 : m-coin; findBestCoinsThatMinimizeAverage(remainingM, n, coins, !minimize); } }

Here is my solution to it: https://dotnetfiddle.net/qnCdop Exponential time complexity. BTW for M=100, N=4 I get {38, 11, 3, 1}, not {1, 5, 18, 25} as the question specifies. One of us is wrong.

## Add Answers or Comments

To comment on this, Sign In or Sign Up.

I just started working on this problem, but here is a rough outline: 1. Generate all subsets of N coins. 2. For each subset, generate the minimum multi-set required to materialize the total values 1...M; say for subset of coins N(i), we name each multi-set of coins N(i),M(j) where j is some value between 1 and M. 3. For fixed i, get the average over j for each multi-set N(i),M(j). 4. Choose the subset N(i) that maps to the lowest average size of the multi-sets that are generated from N(i). Time will be O(2^N), since we are generating each subset of N. Feedback much encouraged to get this down to a polynomial solution.