Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 350
Good morning! Here's your coding interview problem for today.

This problem was asked by Uber.

Write a program that determines the smallest number of perfect squares that sum up to `N`.

Here are a few examples:
```
Given N = 4, return 1 (4)
Given N = 17, return 2 (16 + 1)
Given N = 18, return 2 (9 + 9)
```

Pull request:
Day350
Resolves #695.

Patch:
diff --git a/README.md b/README.md
index ff0d3c7..75a020e 100644
--- a/README.md
+++ b/README.md
@@ -336,3 +336,4 @@ problems from
 * [Day 345](https://github.com/vaskoz/dailycodingproblem-go/issues/687)
 * [Day 346](https://github.com/vaskoz/dailycodingproblem-go/issues/688)
 * [Day 347](https://github.com/vaskoz/dailycodingproblem-go/issues/689)
+* [Day 350](https://github.com/vaskoz/dailycodingproblem-go/issues/695)
diff --git a/day350/problem.go b/day350/problem.go
new file mode 100644
index 0000000..482a0f4
--- /dev/null
+++ b/day350/problem.go
@@ -0,0 +1,51 @@
+package day350
+
+import "math"
+
+// SmallestNumberOfPerfectSquaresSum returns the number
+// of perfect squares that sum up to N.
+// Runs in O(2^N) time.
+func SmallestNumberOfPerfectSquaresSum(n int) int {
+	if n < 4 {
+		return n
+	}
+	res := n
+	for i := 1; i <= n; i++ {
+		tmp := i * i
+		if tmp > n {
+			break
+		} else {
+			res = min(res, 1+SmallestNumberOfPerfectSquaresSum(n-tmp))
+		}
+	}
+	return res
+}
+
+func min(a, b int) int {
+	if a < b {
+		return a
+	}
+	return b
+}
+
+// SmallestNumberOfPerfectSquaresSumFaster returns the number
+// of perfect squares that sum up to N.
+// Runs in O(N) time and uses O(N) space for dynamic programming.
+func SmallestNumberOfPerfectSquaresSumFaster(n int) int {
+	dp := make([]int, n+1)
+	for i := 0; i < 4; i++ {
+		dp[i] = i
+	}
+	for i := 4; i <= n; i++ {
+		dp[i] = i
+		for x := 1; x <= int(math.Ceil(math.Sqrt(float64(i)))); x++ {
+			tmp := x * x
+			if tmp > i {
+				break
+			} else {
+				dp[i] = min(dp[i], 1+dp[i-tmp])
+			}
+		}
+	}
+	return dp[n]
+}


Test patch:
diff --git a/day350/problem_test.go b/day350/problem_test.go
new file mode 100644
index 0000000..f14e1a3
--- /dev/null
+++ b/day350/problem_test.go
@@ -0,0 +1,47 @@
+package day350
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	n        int
+	expected int
+}{
+	{4, 1},
+	{17, 2},
+	{18, 2},
+}
+
+func TestSmallestNumberOfPerfectSquaresSum(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := SmallestNumberOfPerfectSquaresSum(tc.n); result != tc.expected {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkSmallestNumberOfPerfectSquaresSum(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			SmallestNumberOfPerfectSquaresSum(tc.n)
+		}
+	}
+}
+
+func TestSmallestNumberOfPerfectSquaresSumFaster(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := SmallestNumberOfPerfectSquaresSumFaster(tc.n); result != tc.expected {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkSmallestNumberOfPerfectSquaresSumFaster(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			SmallestNumberOfPerfectSquaresSumFaster(tc.n)
+		}
+	}
+}