Given a list of 'N' coins, their values being in an array A[], return the minimum number of coins required to sum to 'S'

__author__ = 'nitin'

import sys

sys.setrecursionlimit(100000)

coins_list=[1,5,10]

def get_coins_sum(given_num,iter_list):
    result_coins=0
    if iter_list>0:
        if given_num>=coins_list[iter_list-1]:
            given_num=given_num- coins_list[iter_list-1]
            if given_num>=coins_list[iter_list-1]:
                result_coins=get_coins_sum(given_num,iter_list)
                result_coins=result_coins+1
            else:
                iter_list=iter_list-1
                result_coins=get_coins_sum(given_num,iter_list)
                result_coins=result_coins+1
        else:
            iter_list=iter_list-1
            result_coins=get_coins_sum(given_num,iter_list)
    return result_coins

if __name__=='__main__':
    iter_list=len(coins_list)
    print get_coins_sum(16,iter_list)

Given an integer between 0 and 99,999, print an English phrase that describes the integer (eg, “One Thousand, Two Hundred and Thirty Four”).

__author__ = 'nitin'

import math

def num_to_string(given_num):
    result_list=[]
    list1=["","One","Two","Three","Four","Five","Six","Seven","Eight","Nine"]
    list11=["","Eleven","Twelve","Thirteen","Fourteen","Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"]
    list10=["","Ten","Twenty","Thirty","Forty","Fifty","Sixty","Seventy","Eighty","Ninety"]
    list100=["","Hundred","Thousand"]
    len=1
    while int(math.pow(10,len))        len=len+1
    if given_num==0:
        result_list.append("Zero")
    else:
        if len>3 and len%2==0:
            len=len+1
        while len>0:
            if len>3:
                tmp=given_num/int(math.pow(10,len-2))
                if tmp/10==1 and tmp%10 !=0:
                    result_list.append(list11[tmp%10])
                else:
                    result_list.append(list10[tmp/10])
                    result_list.append(list1[tmp%10])
                if tmp>0:
                    result_list.append(list100[len/2])
                given_num=given_num % int(math.pow(10,len-2))
                len=len-2
            elif given_num==1000 and len==3:
                result_list.append(list1[len-2])
                result_list.append(list100[len-1])
                len=0
            else:
                tmp=given_num/100
                if tmp!=0:
                    result_list.append(list1[tmp])
                    result_list.append(list100[len/2])
                tmp=given_num%100
                if tmp/10==1 and tmp%10 !=0:
                    result_list.append(list11[tmp%10])
                else:
                    result_list.append(list10[tmp/10])
                    result_list.append(list1[tmp%10])
                len=0
    return " ".join(result_list)

if __name__=="__main__":
    given_num=1000
    print num_to_string(given_num)