Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 399
Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

Given a list of strictly positive integers, partition the list into 3 contiguous partitions which each sum up to the same value. If not possible, return null.

For example, given the following list:

`[3, 5, 8, 0, 8]`
Return the following 3 partitions:
```
[[3, 5],
 [8, 0],
 [8]]
```
Which each add up to 8.

Pull request description:
Day399
Resolves #801.

Patch:
diff --git a/README.md b/README.md
index 86c0901..50cc17b 100644
--- a/README.md
+++ b/README.md
@@ -391,4 +391,5 @@ problems from
 * [Day 396](https://github.com/vaskoz/dailycodingproblem-go/issues/795)
 * [Day 397](https://github.com/vaskoz/dailycodingproblem-go/issues/797)
 * [Day 398](https://github.com/vaskoz/dailycodingproblem-go/issues/799)
+* [Day 399](https://github.com/vaskoz/dailycodingproblem-go/issues/801)
 
diff --git a/day399/problem.go b/day399/problem.go
new file mode 100644
index 0000000..29d32df
--- /dev/null
+++ b/day399/problem.go
@@ -0,0 +1,44 @@
+package day399
+
+import (
+	"errors"
+)
+
+var errNotPossible = errors.New("impossible to get 3 partitions equal")
+
+// PartitionIntoThreeEqualSum tries to partition the input
+// into 3 contiguous sets with equal sums.
+func PartitionIntoThreeEqualSum(nums []int) ([][]int, error) {
+	var sum int
+
+	for _, num := range nums {
+		sum += num
+	}
+
+	target := sum / 3
+
+	if sum%3 != 0 {
+		return nil, errNotPossible
+	}
+
+	ans := make([][]int, 3)
+	pos := 0
+	sum = 0
+
+	for _, num := range nums {
+		sum += num
+
+		switch {
+		case sum < target:
+			ans[pos] = append(ans[pos], num)
+		case sum == target:
+			ans[pos] = append(ans[pos], num)
+			sum = 0
+			pos++
+		default:
+			return nil, errNotPossible
+		}
+	}
+
+	return ans, nil
+}


Test patch:
diff --git a/day399/problem_test.go b/day399/problem_test.go
new file mode 100644
index 0000000..42ac3f2
--- /dev/null
+++ b/day399/problem_test.go
@@ -0,0 +1,52 @@
+package day399
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	input       []int
+	expected    [][]int
+	expectedErr error
+}{
+	{
+		[]int{3, 5, 8, 0, 8},
+		[][]int{
+			{3, 5},
+			{8},
+			{0, 8},
+		},
+		nil,
+	},
+	{
+		[]int{3, 5, 8, 0, 9},
+		nil,
+		errNotPossible,
+	},
+	{
+		[]int{5, 5, 8, 0, 9},
+		nil,
+		errNotPossible,
+	},
+}
+
+func TestPartitionIntoThreeEqualSum(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		if res, err := PartitionIntoThreeEqualSum(tc.input); !reflect.DeepEqual(res, tc.expected) ||
+			tc.expectedErr != err {
+			t.Errorf("Expected(%v,%v), got (%v,%v)", tc.expected, tc.expectedErr, res, err)
+		}
+	}
+}
+
+func BenchmarkPartitionIntoThreeEqualSum(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			PartitionIntoThreeEqualSum(tc.input) // nolint
+		}
+	}
+}