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)
@eyfmharb Thanks!
findCoinDenominations([1, 0, 1, 0, 1, 1, 1, 2, 1, 2, 2]); // => [2, 5, 7]
function findCoinDenominations(realCoinNumCombinations) {
var n = realCoinNumCombinations.length;
var coins = [];
for (var i = 1; i < n; i++)
if (coinNumCombinations(coins, i) < realCoinNumCombinations[i])
coins.push(i)
return coins;
}
function coinNumCombinations(coins, amount) {
var n = amount;
var T = new Array(n+1).fill(0);
T[0] = 1;
for (var denom of coins)
for (var c = 1; c < n+1; c++) {
var amount = c;
if (amount >= denom)
T[amount] += T[amount-denom];
}
return T[n];
}
@arun43 said in Find out the set of denominations:
[1, 0, 1, 0, 1, 1, 1, 2, 1, 2, 2]
Not sure that it's right answer, but it works for the given input. There is some error checking for the input
_list = [1, 0, 1, 0, 1, 1, 1, 2, 1, 2, 2]
# value to index
## 1 0
## 0 1
## 1 2 2
## 0 3
## 1 4 2x2
## 1 5 5
## 1 6 2x3
## 2 7 2 + 5 and 7
## 1 8 2x5
## 2 9 2x2 + 5 and 2 + 7
## 2 10 2x5 and 5x2
# few basic test cases
##_list = [1, 1, 1] # -> [1]
##_list = [1, 1, 2] # -> [1, 2]
##_list = [1, 0, 1] # -> [2]
##_list = [1, 0, 2] # -> exception
##_list = [1, 1, 3] # -> exception
##_list = [1, 0, 1, 0, 1, 1, 1, 2, 1, 2, 3] # -> [2, 5, 7, 10]
def find_set_of_denominations( _list ):
sum_to_ways = {}
coins = []
_len = len( _list )
def add_coin( coin ):
coins.append( coin )
# update sum_to_ways
for i in [ 0 ] + sum_to_ways.keys():
for k in range( coin + i, _len, coin ):
if k not in sum_to_ways:
sum_to_ways[k] = 1
else:
sum_to_ways[k] += 1
if _len > 0:
if _list[0] != 1: # assume empty set can be represented exactly in one way
raise
for i in range( 1, _len ):
_sum = _list[i]
if i not in sum_to_ways:
if _sum > 1:
raise
if _sum == 1:
add_coin( i )
else:
if _sum < sum_to_ways[i] or _sum > sum_to_ways[i] + 1:
raise
if _sum != sum_to_ways[i]:
add_coin( i )
return coins
print find_set_of_denominations( _list )
This can be put into a mathematical question. In general, we test for each number of i in a[i] whether it can be added by the elements in the domain D. If the value of a[i] is greater than possible solutions in domain D, i also belongs to that domain. Here is how we formulate the mathematical problem. Suppose we already have n elements, x1...xn in domain D, we need to solve for b1...bn where b1x1+...bnxn = i. In other words, x1b1+...+xnbn-i=0. From here, if I let matrix A = [x1, ..., xn], Ab-i=0. The NULL Space of A has a rank of n-1. Therefore, if we can find a solution b01, ..., b0n, such that A[b01, b02, ..., b0n]' = i, we have A*(b+b0) = 0. The number of possible solutions is either 0 or n-1. Now the problem becomes whether we can find one solution such that elements in domain D can be added up to i.
Here's a short C# DP solution, O(n^2):
IEnumerable<int> GetDenominations(int[] a) {
int[] ways = new int[a.Length]; ways[0] = 1;
for (int i=1; i<a.Length; i++) {
if (a[i]-ways[i]==1) { // i is a denominator
yield return i;
for (int j=0; j+i<ways.Length; j++) {
if (ways[j]>0)
ways[j+i] += ways[j]; // increment solutions
}
}
}
}
Note incrementing solutions by the # of previous solutions reachable by the next denomination for each new denomination discovered, instead of just by 1 as in @CodingPill's solution #2, which will incorrectly solve larger inputs.
A test case that shows this is:
[1,0,1,0,1,1,1,2,1,2,2,2,3,2,4,3] -> [2,5,7]
@meaty's solution correctly solves this input as well but is O(n^3) due to re-running through all discovered denominations in each round instead of memoizing the previous work.