CODEWITHSUNDEEP
pythonalgorithmlistfunction
FrankieJ
FrankieJ

Reputation: 11

Return number of coins needed of the coin at that position in an array format

I am trying to return the number of coins in an array needed for the sum of a number.

So if m is 143 and coin = [200, 100, 50, 20, 10, 5, 2, 1], it will return [0, 1, 0, 2, 0, 0, 1, 1] meaning no 200-coins, one 100-coin, no 50-coins, two 20-coins, no 10-coins, no 5-coins, one 2-coin and one 1-coin.

Right now my solution returns 5, which is the count of coins.

        def coinSplit(m):
            if m == 0:
                return 0
            for i in range(len(coin)):
                if coin[i] <= m:
                    return 1 + coinSplit(m-coin[i])

      coin = [200, 100, 50, 20, 10, 5, 2, 1]
      print(coinSplit(143))

Upvotes: 1

Views: 294

Answers (3)

user2390182
user2390182

Reputation: 73450

The following iterative implementation works:

def coinSplit(m):
    res = []
    for c in coin:
        num = m // c
        m = m % c
        res.append(num)
    return res

>>> coinSplit(143)
[0, 1, 0, 2, 0, 0, 1, 1]

This assumes a coin pool for which this greedy approach always yields a result. If you want this to be recursive, you can try:

def coinSplit(m, coins):
    if m == 0:
        return [0 for coin in coins]
    return [m // coins[0]] + coinSplit(m % coins[0], coins[1:])

>>> coinSplit(143, [200, 100, 50, 20, 10, 5, 2, 1])
[0, 1, 0, 2, 0, 0, 1, 1]

Upvotes: 3

Farshid
Farshid

Reputation: 31

You are returning number of total coins needed, disregard of their value. You need to keep track of number of each coin which I assume you want to create a list as the same size of your input (coin = [200, 100, 50, 20, 10, 5, 2, 1]) and initialize it with zeros, and as other answer, add to the right index using the modulus and then return this list. You can still write it as recursion but have another operation to add the right index.

I think this is like a homework, so I am not providing the code for you. I hope this helps.

Upvotes: 0

usernamenotfound
usernamenotfound

Reputation: 1580

The key is to use the arithmetic operators in python. Specifically division / and modulus '%'

Get the quotient and remainder by iterating through the list until the remainder is zero.

coin = [200, 100, 50, 20, 10, 5, 2, 1]

for example:

  • 143/200 = 0; 143 % 200 = 143
  • Move on to the next one, 143/100 = 1; 143 % 100 = 43

repeat that process till the remainder is zero

Upvotes: 0

Related Questions