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