Find out the set of denominations

  • 1

    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.


    input: [1, 0, 1, 0, 1, 1, 1, 2, 1, 2, 2] -> output: [2, 5, 7]

  • 2

    Sieve of Eratosthenes

  • 0

    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):

    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]){
    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 :)

  • 1

    @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) {
    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.

  • 0

    @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.

  • 0

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

  • 0


    My bad, should be something more like

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


Log in to reply

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