Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 243
Good morning! Here's your coding interview problem for today.

This problem was asked by Etsy.

Given an array of numbers `N` and an integer `k`, your task is to split `N` into `k` partitions such that the maximum sum of any partition is minimized. Return this sum.

For example, given `N = [5, 1, 2, 7, 3, 4]` and `k = 3`, you should return `8`, since the optimal partition is `[5, 1, 2], [7], [3, 4]`.

Pull request:
Day243
Resolves #502.

Patch:
diff --git a/README.md b/README.md
index b2cac03..45a2c09 100644
--- a/README.md
+++ b/README.md
@@ -254,4 +254,5 @@ problems from
 * [Day 240](https://github.com/vaskoz/dailycodingproblem-go/issues/492)
 * [Day 241](https://github.com/vaskoz/dailycodingproblem-go/issues/493)
 * [Day 242](https://github.com/vaskoz/dailycodingproblem-go/issues/498)
+* [Day 243](https://github.com/vaskoz/dailycodingproblem-go/issues/502)
 * [Day 244](https://github.com/vaskoz/dailycodingproblem-go/issues/503)
diff --git a/day242/problem.go b/day242/problem.go
index f07e0f8..e8dab7c 100644
--- a/day242/problem.go
+++ b/day242/problem.go
@@ -39,7 +39,7 @@ func (r *readOptimized) Query(start, end int) int {
 		panic("start and end must be between 0-23 inclusive")
 	}
 	if start > end {
-		panic("start must precede or equal end")
+		panic("start must preceed or equal end")
 	}
 	r.RLock()
 	var sum int
@@ -76,7 +76,7 @@ func (w *writeOptimized) Query(start, end int) int {
 		panic("start and end must be between 0-23 inclusive")
 	}
 	if start > end {
-		panic("start must precede or equal end")
+		panic("start must preceed or equal end")
 	}
 	w.RLock()
 	var sum int
diff --git a/day243/problem.go b/day243/problem.go
new file mode 100644
index 0000000..e81d76f
--- /dev/null
+++ b/day243/problem.go
@@ -0,0 +1,33 @@
+package day243
+
+// MinimizePartitionMaximumSum returns the smallest max sum of k-partitions.
+func MinimizePartitionMaximumSum(nums []int, k int) int {
+	if k > len(nums) {
+		return 0
+	}
+	return minimizePartitionMaximumSum(nums, k)
+}
+
+func minimizePartitionMaximumSum(nums []int, k int) int {
+	if k == 1 {
+		var sum int
+		for _, v := range nums {
+			sum += v
+		}
+		return sum
+	}
+	minimumMax := int(^uint(0) >> 1)
+	for i := 1; i <= len(nums)-k+1; i++ {
+		var partitionSumMax int
+		for j := 0; j < i; j++ {
+			partitionSumMax += nums[j]
+		}
+		if minMax := minimizePartitionMaximumSum(nums[i:], k-1); minMax > partitionSumMax {
+			partitionSumMax = minMax
+		}
+		if partitionSumMax < minimumMax {
+			minimumMax = partitionSumMax
+		}
+	}
+	return minimumMax
+}


Test patch:
diff --git a/day243/problem_test.go b/day243/problem_test.go
new file mode 100644
index 0000000..6f391e4
--- /dev/null
+++ b/day243/problem_test.go
@@ -0,0 +1,41 @@
+package day243
+
+import "testing"
+
+var testcases = []struct {
+	nums []int
+	k    int
+	sum  int
+}{
+	{[]int{5, 1, 2, 7, 3, 4}, 3, 8},
+	{[]int{3, 1, 1}, 3, 3},
+	{[]int{10, 1, 1}, 4, 0},
+	{[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 6, 11},
+	{[]int{5, 1, 2, 7, 3, 4}, 2, 14},
+	{[]int{5, 1, 2, 7, 3, 4}, 1, 22},
+	{[]int{89, 72, 92, 51, 34, 26, 51, 17, 32, 99}, 10, 99},
+	{[]int{89, 72, 92, 51, 34, 26, 51, 17, 32, 99}, 8, 99},
+	{[]int{89, 72, 92, 51, 34, 26, 51, 17, 32, 99}, 7, 99},
+	{[]int{89, 72, 92, 51, 34, 26, 51, 17, 32, 99}, 6, 111},
+	{[]int{89, 72, 92, 51, 34, 26, 51, 17, 32, 99}, 5, 143},
+	{[]int{89, 72, 92, 51, 34, 26, 51, 17, 32, 99}, 4, 161},
+	{[]int{89, 72, 92, 51, 34, 26, 51, 17, 32, 99}, 3, 203},
+	{[]int{89, 72, 92, 51, 34, 26, 51, 17, 32, 99}, 2, 304},
+}
+
+func TestMinimizePartitionMaximumSum(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if sum := MinimizePartitionMaximumSum(tc.nums, tc.k); sum != tc.sum {
+			t.Errorf("Expected %v, got %v", tc.sum, sum)
+		}
+	}
+}
+
+func BenchmarkMinimizePartitionMaximumSum(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MinimizePartitionMaximumSum(tc.nums, tc.k)
+		}
+	}
+}