Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 384
Good morning! Here's your coding interview problem for today.

This problem was asked by WeWork.

You are given an array of integers representing coin denominations and a total amount of money. Write a function to compute the fewest number of coins needed to make up that amount. If it is not possible to make that amount, return null.

For example, given an array of `[1,5, 10]` and an amount `56`, return `7` since we can use 5 dimes, 1 nickel, and 1 penny.

Given an array of `[5, 8]` and an amount `15`, return `3` since we can use 5 5-cent coins.

Pull request:
Day384
Resolves #776.

Patch:
diff --git a/README.md b/README.md
index 2b7a552..ac83cca 100644
--- a/README.md
+++ b/README.md
@@ -379,5 +379,6 @@ problems from
 * [Day 381](https://github.com/vaskoz/dailycodingproblem-go/issues/768)
 * [Day 382](https://github.com/vaskoz/dailycodingproblem-go/issues/770)
 * [Day 383](https://github.com/vaskoz/dailycodingproblem-go/issues/772)
+* [Day 384](https://github.com/vaskoz/dailycodingproblem-go/issues/776)
 * [Day 385](https://github.com/vaskoz/dailycodingproblem-go/issues/774)
 
diff --git a/day384/problem.go b/day384/problem.go
new file mode 100644
index 0000000..7a68803
--- /dev/null
+++ b/day384/problem.go
@@ -0,0 +1,44 @@
+package day384
+
+import (
+	"errors"
+	"sort"
+)
+
+// nolint
+var errImpossibleTarget = errors.New("impossible to make target change with denominations")
+
+const MaxInt = int(^uint(0) >> 1)
+
+// FewestCoinsBrute returns the fewest required coins to make target
+// in change.
+// Returns an error if it's not possible.
+func FewestCoinsBrute(denom []int, target int) (int, error) {
+	copied := append([]int{}, denom...)
+	sort.Sort(sort.Reverse(sort.IntSlice(copied)))
+
+	return fewestCoinsBrute(copied, target, MaxInt)
+}
+
+func fewestCoinsBrute(denom []int, target, coinsSoFar int) (int, error) {
+	if target < 0 || coinsSoFar < 0 {
+		return 0, errImpossibleTarget
+	} else if target == 0 {
+		return 0, nil
+	}
+
+	smallest := MaxInt
+
+	for _, d := range denom {
+		if res, err := fewestCoinsBrute(denom, target-d, coinsSoFar-1); err == nil && res < smallest {
+			smallest = res
+			coinsSoFar = res
+		}
+	}
+
+	if smallest == MaxInt {
+		return 0, errImpossibleTarget
+	}
+
+	return 1 + smallest, nil
+}


Test patch:
diff --git a/day384/problem_test.go b/day384/problem_test.go
new file mode 100644
index 0000000..99adceb
--- /dev/null
+++ b/day384/problem_test.go
@@ -0,0 +1,33 @@
+package day384
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	denom         []int
+	target        int
+	expectedCoins int
+	expectedErr   error
+}{
+	{[]int{1, 5, 10}, 56, 7, nil},
+	{[]int{5, 8}, 15, 3, nil},
+	{[]int{5, 10}, 2, 0, errImpossibleTarget},
+}
+
+func TestFewestCoinsBrute(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		if res, err := FewestCoinsBrute(tc.denom, tc.target); res != tc.expectedCoins || err != tc.expectedErr {
+			t.Errorf("Expected (%v,%v), got (%v,%v)", tc.expectedCoins, tc.expectedErr, res, err)
+		}
+	}
+}
+
+func BenchmarkFewestCoinsBrute(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			FewestCoinsBrute(tc.denom, tc.target) // nolint
+		}
+	}
+}