# Find out the set of denominations

• 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]

• Sieve of Eratosthenes

• 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:
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:
return
subsetSum(sums_set, nums, left + 1, right, sum + nums[left])
subsetSum(sums_set, nums, left + 1, right, sum)

• @eyfmharb

My bad, should be something more like

for (i=1; i<N; ++i) {
if (a[i] > s[i]) {
coins.push_back(i);
++s[i];
for (int j=i; j+i<N; ++j)
if (s[j] > 0) ++s[j+i];
}
}

O(n^2)

• @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];
}

• [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 )

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:
else:
if _sum < sum_to_ways[i] or _sum > sum_to_ways[i] + 1:
raise
if _sum != sum_to_ways[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.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.