Given an array of length N, where array[i] is the count of ways we can produce the amount i,
find out the set of denominations.
e.g
input: [1, 0, 1, 0, 1, 1, 1, 2, 1, 2, 2] -> output: [2, 5, 7]
Here is an O(n^3) Solution.
First, I will use the function count(coins[], int n) which gives me the number of ways you can write n with the coins in coins[]. You can calculate this using dynamic programming. Here is a link that shows how to do this. It runs in O(n^2):
http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/
Once you have this function as a black box, the solution becomes easy, here is a pseudocode:
Let coins be an empty array
For i=1 to n:
if (count(coins, i) < array[i]){
coins.insert(i)
}
Return coins
This solution should run in total O(n^3) time. I would be happy to know if someone knows what the optimum solution is :)
@eyfmharb See my comment above, the Sieve of Eratosthenes can be O(n log log n) if implemented carefully.
for (i=1; i<N; ++i) {
if (a[i] > 0) {
coins.push_back(i);
for (int j=i; j<N; j+=i) --a[j];
}
}
proving that the complexity is O(n log log n) is quite complicated. You can find the proof if you google it.
@CodingPill Your code doesn't work. Running this on the input provided by OP returns [2,5,7,9]. 9 can be expressed as the sum of 2,2,5. However, 9 doesn't divide 2 or 5 so your logic here is incorrect.
@eyfmharb Yes, I tried it too. I get the 9 in my set too.
def getDenominations(nums):
len_of_nums = len(nums)
denominations = set()
for i in xrange(1, len_of_nums):
if nums[i] != 0:
denominations.add(i)
strikeMultiples(i, nums)
if len(list(denominations)) > 1:
sums_set = set()
subsetSum(sums_set,list(denominations),0, len(list(denominations)) - 1)
for x in list(sums_set):
if x > i and x < len_of_nums:
nums[x] -= 1
print list(denominations)
def strikeMultiples(val, nums):
original_val = val
while (val <= len(nums)):
if nums[val] > 0:
nums[val] -= 1
val += original_val
def subsetSum(sums_set, nums, left, right, sum=0):
if left > right:
sums_set.add(sum)
return
subsetSum(sums_set, nums, left + 1, right, sum + nums[left])
subsetSum(sums_set, nums, left + 1, right, sum)