Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 61
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Implement integer exponentiation. That is, implement the pow(x, y) function, where x and y are integers and returns x^y.

Do this faster than the naive method of repeated multiplication.

For example, pow(2, 10) should return 1024.

Pull request description:
Day61
Resolves #132.

Patch:
diff --git a/README.md b/README.md
index f0cc99f..d09388f 100644
--- a/README.md
+++ b/README.md
@@ -71,3 +71,4 @@ problems from
 * [Day 57](https://github.com/vaskoz/dailycodingproblem-go/issues/124)
 * [Day 58](https://github.com/vaskoz/dailycodingproblem-go/issues/127)
 * [Day 60](https://github.com/vaskoz/dailycodingproblem-go/issues/130)
+* [Day 61](https://github.com/vaskoz/dailycodingproblem-go/issues/132)
diff --git a/day61/problem.go b/day61/problem.go
new file mode 100644
index 0000000..8ec58bb
--- /dev/null
+++ b/day61/problem.go
@@ -0,0 +1,31 @@
+package day61
+
+// NaiveIntegerExponentiation returns the result of x^y by calculating it
+// naively. Runs in O(y) time due to y multiplications of x.
+// y must be 0 or greater otherwise will panic.
+func NaiveIntegerExponentiation(x, y uint) uint {
+	result := uint(1)
+	for i := uint(0); i < y; i++ {
+		result *= x
+	}
+	return result
+}
+
+// IntegerExponentiationBySquaring calculates x^y.
+// Runs in O(log y) time.
+func IntegerExponentiationBySquaring(x, y uint) uint {
+	if y == 0 {
+		return 1
+	}
+	z := uint(1)
+	for y > 1 {
+		if y%2 == 0 {
+			y /= 2
+		} else {
+			z *= x
+			y = (y - 1) / 2
+		}
+		x *= x
+	}
+	return x * z
+}


Test patch:
diff --git a/day61/problem_test.go b/day61/problem_test.go
new file mode 100644
index 0000000..4d20b32
--- /dev/null
+++ b/day61/problem_test.go
@@ -0,0 +1,46 @@
+package day61
+
+import "testing"
+
+var testcases = []struct {
+	x, y, expected uint
+}{
+	{2, 10, 1024},
+	{2, 1, 2},
+	{2, 0, 1},
+	{2, 62, 4611686018427387904},
+}
+
+func TestNaiveIntegerExponentiation(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := NaiveIntegerExponentiation(tc.x, tc.y); result != tc.expected {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkNaiveIntegerExponentiation(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			NaiveIntegerExponentiation(tc.x, tc.y)
+		}
+	}
+}
+
+func TestIntegerExponentiationBySquaring(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := IntegerExponentiationBySquaring(tc.x, tc.y); result != tc.expected {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkIntegerExponentiationBySquaring(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			IntegerExponentiationBySquaring(tc.x, tc.y)
+		}
+	}
+}