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)


  • 0
    M

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

  • 0
    4

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

  • 0
    S

    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.


  • 0
    M

    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.


Log in to reply
 

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