Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 336
Good morning! Here's your coding interview problem for today.

This problem was asked by Microsoft.

Write a program to determine how many distinct ways there are to create a max heap from a list of N given integers.

For example, if `N = 3`, and our integers are `[1, 2, 3]`, there are two ways, shown below.
```
  3      3
 / \    / \
1   2  2   1
```

Pull request:
Day336
Resolves #673.

Patch:
diff --git a/README.md b/README.md
index f59e5e5..4656b05 100644
--- a/README.md
+++ b/README.md
@@ -342,6 +342,7 @@ problems from
 * [Day 332](https://github.com/vaskoz/dailycodingproblem-go/issues/669)
 * [Day 333](https://github.com/vaskoz/dailycodingproblem-go/issues/668)
 * [Day 334](https://github.com/vaskoz/dailycodingproblem-go/issues/670)
+* [Day 336](https://github.com/vaskoz/dailycodingproblem-go/issues/673)
 * [Day 337](https://github.com/vaskoz/dailycodingproblem-go/issues/674)
 * [Day 338](https://github.com/vaskoz/dailycodingproblem-go/issues/675)
 * [Day 339](https://github.com/vaskoz/dailycodingproblem-go/issues/676)
diff --git a/day336/problem.go b/day336/problem.go
new file mode 100644
index 0000000..cb338f3
--- /dev/null
+++ b/day336/problem.go
@@ -0,0 +1,93 @@
+package day336
+
+// PossibleMaxHeaps returns a count of all possible
+// max heaps.
+func PossibleMaxHeaps(n int) int {
+	dp := make([]int, n+1)
+
+	for i := range dp {
+		dp[i] = -1
+	}
+
+	nck := make([][]int, n+1)
+
+	for i := range nck {
+		nck[i] = make([]int, n+1)
+		for j := range nck[i] {
+			nck[i][j] = -1
+		}
+	}
+
+	currLog2 := -1
+	currPower2 := 1
+	log2 := make([]int, n+1)
+
+	for i := 1; i <= n; i++ {
+		if currPower2 == i {
+			currLog2++
+
+			currPower2 *= 2
+		}
+
+		log2[i] = currLog2
+	}
+
+	return numberOfHeaps(n, dp, log2, nck)
+}
+
+func numberOfHeaps(n int, dp, log2 []int, nck [][]int) int {
+	if n <= 1 {
+		return 1
+	}
+
+	if dp[n] != -1 {
+		return dp[n]
+	}
+
+	left := getLeft(n, log2)
+	ans := choose(n-1, left, nck) *
+		numberOfHeaps(left, dp, log2, nck) *
+		numberOfHeaps(n-1-left, dp, log2, nck)
+	dp[n] = ans
+
+	return ans
+}
+
+func getLeft(n int, log2 []int) int {
+	if n == 1 {
+		return 0
+	}
+
+	h := log2[n]
+	numh := 1 << h
+	last := n - ((1 << h) - 1)
+
+	if last >= numh/2 {
+		return (1 << h) - 1
+	}
+
+	return (1 << h) - 1 - ((numh / 2) - last)
+}
+
+func choose(n, k int, nck [][]int) int {
+	if k > n {
+		return 0
+	}
+
+	if n <= 1 {
+		return 1
+	}
+
+	if k == 0 {
+		return 1
+	}
+
+	if nck[n][k] != -1 {
+		return nck[n][k]
+	}
+
+	answer := choose(n-1, k-1, nck) + choose(n-1, k, nck)
+	nck[n][k] = answer
+
+	return answer
+}


Test patch:
diff --git a/day336/problem_test.go b/day336/problem_test.go
new file mode 100644
index 0000000..9740cc7
--- /dev/null
+++ b/day336/problem_test.go
@@ -0,0 +1,29 @@
+package day336
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	n, expected int
+}{
+	{10, 3360},
+	{3, 2},
+}
+
+func TestPossibleMaxHeaps(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		if res := PossibleMaxHeaps(tc.n); res != tc.expected {
+			t.Errorf("Expected %v, got %v", tc.expected, res)
+		}
+	}
+}
+
+func BenchmarkPossibleMaxHeaps(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			PossibleMaxHeaps(tc.n)
+		}
+	}
+}