1
$\begingroup$

was doing coin change problem as an assignment(didnt know before), after came with this solution i checked the solutions available couldnt find a similar one like this, just curious. removing the element from the list is O(N) so seems this also O(N^2) right?

def rec_coin(target,coins):
    if target == 0 or coins == []:
        return 0

    max_coin = max(coins)
    mod = target % max_coin
    coin_count = (target-mod)/ max_coin
    coins.remove(max_coin)

    return int(coin_count) + rec_coin(mod, coins)

rec_coin(23,[1,5,10,25])
|cite|improve this question
$\endgroup$

closed as unclear what you're asking by David Richerby, Evil, Yuval Filmus, Discrete lizard♦, Tom van der Zanden Aug 31 '18 at 11:12

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ See cs.stackexchange.com/q/23593/755 for how you can solve it yourself. We can't tell you how long it takes to remove an element from a list, because that depends on the programming language and how the list is implemented (as a linked list? balanced binary tree? hashtable?); coding and language-specific questions are off-topic here. $\endgroup$ – D.W.♦ Aug 20 '18 at 21:43
  • $\begingroup$ Sorry, but it's your TA or professor's job to grade your homework assignments, not ours. $\endgroup$ – David Richerby Aug 20 '18 at 22:49