Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 316
Good morning! Here's your coding interview problem for today.

This problem was asked by Snapchat.

You are given an array of length N, where each element i represents the number of ways we can produce i units of change. For example, `[1, 0, 1, 1, 2]` would indicate that there is only one way to make `0`, `2`, or `3` units, and two ways of making 4 units.

Given such an array, determine the denominations that must be in use. In the case above, for example, there must be coins with value `2, 3, and 4`.

Pull request description:
Day316
Resolves #644.

Patch:
diff --git a/README.md b/README.md
index c05c33b..0ff32a8 100644
--- a/README.md
+++ b/README.md
@@ -326,6 +326,7 @@ problems from
 * [Day 313](https://github.com/vaskoz/dailycodingproblem-go/issues/639)
 * [Day 314](https://github.com/vaskoz/dailycodingproblem-go/issues/640)
 * [Day 315](https://github.com/vaskoz/dailycodingproblem-go/issues/642)
+* [Day 316](https://github.com/vaskoz/dailycodingproblem-go/issues/644)
 * [Day 317](https://github.com/vaskoz/dailycodingproblem-go/issues/645)
 * [Day 320](https://github.com/vaskoz/dailycodingproblem-go/issues/650)
 * [Day 321](https://github.com/vaskoz/dailycodingproblem-go/issues/651)
diff --git a/day316/problem.go b/day316/problem.go
new file mode 100644
index 0000000..c65a90f
--- /dev/null
+++ b/day316/problem.go
@@ -0,0 +1,43 @@
+package day316
+
+import (
+	"sort"
+)
+
+// CoinDenominationsNeeded returns the required denominations
+// to achieve the number of ways to make change.
+func CoinDenominationsNeeded(ways []int) []int {
+	denoms := make(map[int]struct{})
+
+	for d, way := range ways {
+		if others := waysToProduce(d, denoms); (way == 1 && d > 0) || others == way-1 {
+			denoms[d] = struct{}{}
+		}
+	}
+
+	res := make([]int, 0, len(denoms))
+
+	for k := range denoms {
+		res = append(res, k)
+	}
+
+	sort.Ints(res)
+
+	return res
+}
+
+func waysToProduce(target int, denoms map[int]struct{}) int {
+	if _, found := denoms[target]; found || target == 0 {
+		return 1
+	}
+
+	ways := 0
+
+	for k := range denoms {
+		if target%k == 0 {
+			ways += waysToProduce(target/k, denoms)
+		}
+	}
+
+	return ways
+}


Test patch:
diff --git a/day316/problem_test.go b/day316/problem_test.go
new file mode 100644
index 0000000..b29e108
--- /dev/null
+++ b/day316/problem_test.go
@@ -0,0 +1,31 @@
+package day316
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	ways, denoms []int
+}{
+	{[]int{1, 0, 1, 1, 2}, []int{2, 3, 4}},
+}
+
+func TestCoinDenominationsNeeded(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		if res := CoinDenominationsNeeded(tc.ways); !reflect.DeepEqual(res, tc.denoms) {
+			t.Errorf("Expected %v, got %v", tc.denoms, res)
+		}
+	}
+}
+
+func BenchmarkCoinDenominationsNeeded(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			CoinDenominationsNeeded(tc.ways)
+		}
+	}
+}