Find out the set of denominations


  • 1
    A

    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]


  • 2
    C

    Sieve of Eratosthenes


  • 0
    E

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


  • 1
    C

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


  • 0
    E

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

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

  • 0
    C

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


Log in to reply
 

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