Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 233
Good morning! Here's your coding interview problem for today.

This problem was asked by Apple.

Implement the function `fib(n)`, which returns the nth number in the Fibonacci sequence, using only `O(1)` space.

Pull request description:
Day233
Resolves #479.

Patch:
diff --git a/README.md b/README.md
index 05a4d52..72fdbc9 100644
--- a/README.md
+++ b/README.md
@@ -241,3 +241,4 @@ problems from
 * [Day 230](https://github.com/vaskoz/dailycodingproblem-go/issues/473)
 * [Day 231](https://github.com/vaskoz/dailycodingproblem-go/issues/475)
 * [Day 232](https://github.com/vaskoz/dailycodingproblem-go/issues/477)
+* [Day 233](https://github.com/vaskoz/dailycodingproblem-go/issues/479)
diff --git a/day233/problem.go b/day233/problem.go
new file mode 100644
index 0000000..528e223
--- /dev/null
+++ b/day233/problem.go
@@ -0,0 +1,27 @@
+package day233
+
+import "errors"
+
+var errOverflow = errors.New("overflow occurred")
+
+// ErrOverflow represents an overflow error.
+func ErrOverflow() error {
+	return errOverflow
+}
+
+// FastFibonnaci runs in O(N) time with O(1) space.
+// Returns an error if overflow occurs.
+func FastFibonnaci(n uint) (uint, error) {
+	if n < 2 {
+		return n, nil
+	}
+	first, second := uint(0), uint(1)
+	var err error
+	for i := uint(1); i < n; i++ {
+		first, second = second, first+second
+		if second < first {
+			return 0, errOverflow
+		}
+	}
+	return second, err
+}


Test patch:
diff --git a/day233/problem_test.go b/day233/problem_test.go
new file mode 100644
index 0000000..9d05d0f
--- /dev/null
+++ b/day233/problem_test.go
@@ -0,0 +1,34 @@
+package day233
+
+import "testing"
+
+var testcases = []struct {
+	n, fib uint
+	err    error
+}{
+	{0, 0, nil},
+	{1, 1, nil},
+	{2, 1, nil},
+	{12, 144, nil},
+	{28, 317811, nil},
+	{44, 701408733, nil},
+	{87, 679891637638612258, nil},
+	{100, 0, ErrOverflow()},
+}
+
+func TestFastFibonnaci(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result, err := FastFibonnaci(tc.n); result != tc.fib || err != tc.err {
+			t.Errorf("Given n=%d, expected (%d,%v), got (%d,%v)", tc.n, tc.fib, tc.err, result, err)
+		}
+	}
+}
+
+func BenchmarkFastFibonnaci(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			FastFibonnaci(tc.n) //nolint
+		}
+	}
+}