settleDebt.py

def settleDebt(debt_dict):
    """
    Function to settle debt among group of people
    
    Parameters
    ----------
    debt_dict : dictionary of names and debt(expenses-paid)
        sum of debts should be approximately zero
        -ve means negative debt, +ve means positive debt
    
    Returns
    -------
    transactions
        list of transactions to be performed
    error 
        error introduced due to rounding off
    """
    assert abs(sum(debt_dict.values()))<1, "Sum of Debt should less than 1"
    debt = [ [ bal,name ] for name,bal in debt_dict.items() ]
    debt = sorted(debt, key=lambda x: x[0])
    i=0;j=len(debt)-1
    transactions = []
    total = 0;tobepaid = 0
    while i<j:
        if debt[i][0]==0: i+=1; continue
        if debt[j][0]==0: j-=1; continue
        if abs(debt[i][0]) == abs(debt[j][0]):
            total += abs(debt[j][0]); tobepaid+=round(abs(debt[j][0]))
            transactions.append( debt[j][1]+' -> '+debt[i][1]+f" : {round(abs(debt[j][0]))}")
            debt[i][0], debt[j][0] = 0,0
            i+=1;j-=1;
        elif abs(debt[i][0]) > abs(debt[j][0]):
            total += abs(debt[j][0]); tobepaid+=round(abs(debt[j][0]))
            transactions.append( debt[j][1]+' -> '+debt[i][1]+f" : {round(abs(debt[j][0]))}" )
            debt[i][0], debt[j][0] = debt[i][0]+debt[j][0],0
            j-=1
        else:
            total += abs(debt[i][0]); tobepaid+=round(abs(debt[i][0]))
            transactions.append( debt[j][1]+' -> '+debt[i][1]+f" : {round(abs(debt[i][0]))}" )
            debt[i][0], debt[j][0] = 0,debt[i][0]+debt[j][0]
            i+=1
    return transactions, tobepaid-total

debt = { 'A' : 500, 'B':-50, 'C':320, 'D':-140, 'E':-310, 'F':-130, 'G':-190}
transactions, error = settleDebt(debt)