Minimum number of bills or coins in change (golang)

Updated vegaseat 1 499 Views

This Go snippet calculates the minimum number of bills or coins needed for a given amount of money (change) requested. The program also gives the denomination and number. US curency is used in this example, but can be changed to another currency.

// minimum_change.go
//
// for a given amount of change (in cents)
// calculate the minimum number of bills or coins needed
// using a csv string converted to a structure
//
// for imported package info see ...
// http://golang.org/pkg/fmt/
// http://golang.org/pkg/strconv/
// http://golang.org/pkg/strings/
//
// online play at:
// http://play.golang.org/p/-bW65AQw-Q
//
// tested with Go version 1.4.2   by vegaseat (dns) 9may2015

package main

import (
	"fmt"
	"strconv"
	"strings"
)

type USmoney struct {
	cents int
	name  string
}

func main() {
	fmt.Println("Minimum number of bills and coins:\n")

	// change requested in cents
	change := 888
	fmt.Printf("Change requested = %d cents\n", change)
	fmt.Println("----------------------------")

	// half dollar is rare and not used
	// cents,name on each line
	csv_us_money := `10000,Hundred Dollars
5000,Fifty Dollars
2000,Twenty Dollars
1000,Ten Dollars
500,Five Dollars
100,Dollars
25,Quarters
10,Dimes
5,Nickels
1,Pennies`

	// split at the newline char to create a slice of lines
	slice_lines := strings.Split(csv_us_money, "\n")
	// create pointer to an instance of structure USmoney
	pstu := new(USmoney)
	// now create a slice of structures	using the pointer
	slice_struct := make([]USmoney, len(slice_lines))
	for ix, line := range slice_lines {
		// split at the comma
		cents_name := strings.Split(line, ",")
		pstu.cents, _ = strconv.Atoi(cents_name[0])
		pstu.name = cents_name[1]
		slice_struct[ix] = *pstu
	}

	bills_coins := 0
	for _, money := range slice_struct {
		whole := change / money.cents
		remain := change % money.cents
		change = remain
		fmt.Printf("%-15s = %d\n", money.name, whole)
		bills_coins += whole
	}
	fmt.Println("----------------------------")
	fmt.Printf("A total of %d bills or coins\n", bills_coins)

}

/* result ...
Minimum number of bills and coins:

Change requested = 888 cents
----------------------------
Hundred Dollars = 0
Fifty Dollars   = 0
Twenty Dollars  = 0
Ten Dollars     = 0
Five Dollars    = 1
Dollars         = 3
Quarters        = 3
Dimes           = 1
Nickels         = 0
Pennies         = 3
----------------------------
A total of 11 bills or coins
*/

Dani AI

Generated

Good, compact greedy solution from that parses a CSV of denominations into a struct slice and uses integer arithmetic to compute counts. That pattern is simple, fast and correct for standard U.S. bills and coins because the common denomination set is canonical. The example is a useful teaching piece and a practical baseline for fixed, well-behaved currency sets.

Make the implementation more robust and idiomatic: validate conversions returned by strconv.Atoi; trim CSV fields before use; avoid repeatedly reusing a single pointer when building the slice (append composite-literal structs instead); and ensure denominations are sorted in descending order prior to the greedy pass. Add defensive checks for zero or duplicate denominations and handle negative or zero amounts gracefully. If parsing will come from files or user input, use a scanner and clear error reporting.

Important caveat: greedy is not universal. For arbitrary denomination sets greedy can produce a suboptimal result — e.g. denominations [1,3,4] and target 6: greedy picks 4+1+1 (3 coins) while the optimal solution is 3+3 (2 coins). For general correctness use a dynamic-programming approach. The following Go-style routine computes the minimum coin count in O(amount * m) time (m = number of denominations):

func minCoins(amount int, denoms []int) int {
    if amount < 0 { return -1 }
    dp := make([]int, amount+1)
    for i := 1; i <= amount; i++ {
        dp[i] = amount + 1
        for _, d := range denoms {
            if d <= i && dp[i-d]+1 < dp[i] {
                dp[i] = dp[i-d] + 1
            }
        }
    }
    if dp[amount] > amount { return -1 } // no solution
    return dp[amount]
}

For full solutions that also return which coins were used, keep a predecessor array while filling dp and backtrack. Add unit tests that exercise canonical and non-canonical sets, boundary values, and very large amounts to check memory. The original by is a solid baseline; these changes make it safer and easier to adapt to other currencies or arbitrary denomination rules.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview