Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 138
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Find the minimum number of coins required to make n cents.

You can use standard American denominations, that is, 1¢, 5¢, 10¢, and 25¢.

For example, given n = 16, return 3 since we can make it with a 10¢, a 5¢, and a 1¢.

Pull request:
Day138
Resolves #286.

Patch:
diff --git a/README.md b/README.md
index 66773eb..c773d8f 100644
--- a/README.md
+++ b/README.md
@@ -146,4 +146,5 @@ problems from
 * [Day 135](https://github.com/vaskoz/dailycodingproblem-go/issues/280)
 * [Day 136](https://github.com/vaskoz/dailycodingproblem-go/issues/282)
 * [Day 137](https://github.com/vaskoz/dailycodingproblem-go/issues/285)
+* [Day 138](https://github.com/vaskoz/dailycodingproblem-go/issues/286)
 * [Day 139](https://github.com/vaskoz/dailycodingproblem-go/issues/288)
diff --git a/day138/problem.go b/day138/problem.go
new file mode 100644
index 0000000..0f7c1f2
--- /dev/null
+++ b/day138/problem.go
@@ -0,0 +1,61 @@
+package day138
+
+import (
+	"errors"
+)
+
+var errNotPossible = errors.New("Can not make this value")
+
+// ErrNotPossible represents that making this currency with these
+// denominations is impossible.
+func ErrNotPossible() error {
+	return errNotPossible
+}
+
+// MinCurrencyRequiredBrute returns the minimum number of currency
+// necessary to make the desired amount.
+func MinCurrencyRequiredBrute(amt int, denomCents []int) (int, error) {
+	if amt < 0 {
+		return 0, errNotPossible
+	} else if amt == 0 {
+		return 0, nil
+	}
+	min := int(^uint(0) >> 1)
+	found := false
+	for _, denom := range denomCents {
+		if count, err := MinCurrencyRequiredBrute(amt-denom, denomCents); err == nil && count+1 < min {
+			found = true
+			min = count + 1
+		}
+	}
+	if found {
+		return min, nil
+	}
+	return 0, errNotPossible
+}
+
+// MinCurrencyRequiredSmarter returns the minimum number of currency
+// necessary to make the desired amount.
+func MinCurrencyRequiredSmarter(amt int, denomCents []int) (int, error) {
+	return minCurrencyRequiredSmarter(amt, int(^uint(0)>>1), 0, denomCents)
+}
+
+func minCurrencyRequiredSmarter(amt, min, count int, denomCents []int) (int, error) {
+	if count > min || amt < 0 {
+		return 0, errNotPossible
+	} else if amt == 0 {
+		return count, nil
+	}
+	found := false
+	for i := range denomCents {
+		current := denomCents[len(denomCents)-1-i]
+		if result, err := minCurrencyRequiredSmarter(amt-current, min, count+1, denomCents); err == nil && result < min {
+			found = true
+			min = result
+		}
+	}
+	if found {
+		return min, nil
+	}
+	return 0, errNotPossible
+}


Test patch:
diff --git a/day138/problem_test.go b/day138/problem_test.go
new file mode 100644
index 0000000..9fff0ab
--- /dev/null
+++ b/day138/problem_test.go
@@ -0,0 +1,49 @@
+package day138
+
+import "testing"
+
+var testcases = []struct {
+	denom    []int
+	n        int
+	expected int
+	err      error
+}{
+	{[]int{1, 5, 10, 25}, 16, 3, nil},
+	{[]int{25}, 16, 0, ErrNotPossible()},
+	{[]int{2, 5}, 16, 5, nil},
+	{[]int{2, 3, 6}, 6, 1, nil},
+}
+
+func TestMinCurrencyRequiredBrute(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result, err := MinCurrencyRequiredBrute(tc.n, tc.denom); err != tc.err || result != tc.expected {
+			t.Errorf("Expected (%v,%v) got (%v,%v)", tc.expected, tc.err, result, err)
+		}
+	}
+}
+
+func BenchmarkMinCurrencyRequiredBrute(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MinCurrencyRequiredBrute(tc.n, tc.denom)
+		}
+	}
+}
+
+func TestMinCurrencyRequiredSmarter(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result, err := MinCurrencyRequiredSmarter(tc.n, tc.denom); err != tc.err || result != tc.expected {
+			t.Errorf("Expected (%v,%v) got (%v,%v)", tc.expected, tc.err, result, err)
+		}
+	}
+}
+
+func BenchmarkMinCurrencyRequiredSmarter(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MinCurrencyRequiredSmarter(tc.n, tc.denom)
+		}
+	}
+}