Minimum Number Of Coins To make Change

minNoCoinsChange.py

#-----------------------------------------------------
#--------Minimum Number Of Coins For Change-----------
#-----------------------------------------------------

'''
Logic

    Suppose we are asked to make change of 24 and denomination given are [10,5,2,1]
    Let total_coins = 0

    Starting from 10
    24 // 10 = 2  --> This means we can use 2 coins of so update total_coins = 2
    24 % 10 = 4   --> Now amount reduced to 4 

    Now take 5
    5 is greater than the amount left (i.e 4) so we won't use it

    Now take 2
    4 // 2 = 2     --> This we can use 2 coins , so update total_coins = 4
    4 % 2 = 0      --> Now amount reduced to 

    As amount became 0 so we can stop loop

    return total_coins = 4
'''


def minNoCoinsChange(array,amount):
    result = float("inf")
    array = sorted(array,reverse=True)
    length = len(array)
    flag = False
    for i in range(length):
        coins = 0
        temp_amt = amount
        for j in range(i,length):
            if temp_amt == 0 : 
                flag = True
                break
            if array[j] <= temp_amt:
                coins += temp_amt//array[j]
                temp_amt = temp_amt%array[j]
        result = min(result,coins)
    return result if flag is True else -1          
    
print(minNoCoinsChange([2,4],7))

'''

Dynamic Programming :

Logic : 

    Suppose we are asked to make amount 5 from denomination [4,2,1,3]

    We take a result array of size amount+1 i.e. 5+1 = 6

     $0  $1  $2  $3  $4  $5
    [ _ , _ , _ , _ , _ , _ ]        // empty spaces are infinity

    to make $0 we need 0 coins, so    
     $0  $1  $2  $3  $4  $5
    [ 0 , _ , _ , _ , _ , _ ]  

    -----------------------------------------------------------------------------------

    Now lets start with $4 our first coin. We will iterate over our result array now
        > With $4 coin we can not make $1 as $1 not <= $4, so no change at index 1
        > With $4 coin we can not make $2 as $2 not <= $4, so no change at index 2
        > With $4 coin we can not make $3 as $1 not <= $4, so no change at index 3
        > WIth $4 coin we can make $4 as $4 <= $4, So we see:
            1. either current value at the index 4 i.e. nothing (infinity)
            2. or If we use $4 coin to make $4 then how much amount is left i.e. 4-4 = $0. 
               Now we will see from our reult array how many coins it need to make 0$ from $0 coin (i.e. 0)
               so to make $4 from $4 we used 1 + 0 coin
            let's now see minimum of above to case i.e. 1 , so we set index 4 as 1

         $0  $1  $2  $3  $4  $5
        [ 0 , _ , _ , _ , 1 , _ ]

        > with $4 coin can I make $5 ?  Cases:
            1. Value at index 5 i.e infinity
            2. If we choose $4 coin to make $5 then we are left with 5-4 $1 amount. 
               Now we will see how many coins it need to make $1 from $1 i.e. infinity
               so to make $5 from $4 coin we used 1+ infinity coin
            minimum of all cases is infinity, so no change at index 5

        $0  $1  $2  $3  $4  $5
        [ 0 , _ , _ , _ , 1 , _ ]

    --------------------------------------------------------------------------------------

    Now lets take $2
        > with $2 can we make $1? No, so index 1 remain same
        > with $2 can we make $2?, Yes so now we will see
            1. Current value at index i.e infinity
            2. If we choose $2 coin to make $2 we are left with 2-2 $0 amount. 
               To make $0 from $0 we need 0 coins
               so in total we used 1+0 coins
            minimum of these cases is 1, so index 2 gets updated

        $0  $1  $2  $3  $4  $5
        [ 0 , _ , 1 , _ , 1 , _ ]

        > with $2 coin we can not make $3 so no changes
        > with $2 we can make $4?, Yes. We Will see:
            1. Current value i.e. 1
            2. If we $2 to make $4 we are left with 4-2 $2.
               To make $2 from $2 we need 1 coin (from our result array)
               So in total we need 1+1 coin
            minimum of these cases is 1, index 4 is set to 1 (unchanged)

    Similarly with $1 coin and $3 coin

    al last our result array will be

    [0, 1, 1, 1, 1, 2]



    Formula :
        if coin_value <= current_amount:
            result [current_amount] = min(
                result[current_amount] , 
                result [current_amount - coin_value] +1
            )
        

'''

def minNoCoinsChange1(array,amount):
    result = [float("inf") for n in range(amount + 1)]
    result[0] = 0
    for coin in array:
        for amt in range(coin,len(result)):
            #print(result, coin, amt)
            result[amt] = min(result[amt], result[amt-coin]+1)
    return result[-1] if result[-1] < float("inf") else -1

print(minNoCoinsChange1([4,2,1,3], 5))

'''

Recursive solution



                                    {[4,2,1,3],-3} Rejected

                                    {[4,2,1,3],-1} Rejected
                    {[4,2,1,3],1}    
                                    {[4,2,1,3], 0} ------ Return 0

                                    {[4,2,1,3],-2} Rejected



                                                    {[4,2,1,3],-3} rejected

                                                    {[4,2,1,3],-1} rejected
                                    {[4,2,1,3],1}
                                                    {[4,2,1,3],0} ----------Return 0

                                                    {[4,2,1,3],-2} Rejected
                    {[4,2,1,3],3}
                                    {[4,2,1,3],-1} Rejected
    
                                    {[4,2,1,3],-2} Rejected 

                                    {[4,2,1,3],0} --------Return 0


    {[4,2,1,3],5} 

    
                                    {[4,2,1,3],0} -----------Return 0

                                    {[4,2,1,3],-2} Rejected
                    {[4,2,1,3],4}
                                    {[4,2,1,3],-3} Rejected

                                    {[4,2,1,3],-1} Rejected


                                                        

                                    {[4,2,1,3],-2} Rejected

                                    {[4,2,1,3],0} --------Return 0
                    
                                                    {[4,2,1,3],-3} rejected
                    {[4,2,1,3],2}
                                                    {[4,2,1,3],-1} rejected
                                    {[4,2,1,3],1}
                                                    {[4,2,1,3],0} ----------Return 0

                                                    {[4,2,1,3],-2} Rejected

                                    {[4,2,1,3],-1} Rejected



    we will return the least depth.
    In this case it is 2
    
  
'''

def minNoCoinsChange2(array,n,v):
    if v == 0:
        return 0     
    result = float("inf")
    for i in range(0,n):
        if array[i] <= v:
            current = minNoCoinsChange2(array,n,v-array[i])
            if current != float("inf") and current + 1 < result:
                result = current + 1
    
    return result

print(minNoCoinsChange2([4,2,1,3],4,5))