Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 268
Good morning! Here's your coding interview problem for today.

This problem was asked by Indeed.

Given a 32-bit positive integer `N`, determine whether it is a power of four in faster than `O(log N)` time.

Pull request description:
Day268
Resolves #544.

Patch:
diff --git a/README.md b/README.md
index 9c8da9f..fb93a8a 100644
--- a/README.md
+++ b/README.md
@@ -271,3 +271,4 @@ problems from
 * [Day 257](https://github.com/vaskoz/dailycodingproblem-go/issues/529)
 * [Day 258](https://github.com/vaskoz/dailycodingproblem-go/issues/530)
 * [Day 260](https://github.com/vaskoz/dailycodingproblem-go/issues/533)
+* [Day 268](https://github.com/vaskoz/dailycodingproblem-go/issues/544)
diff --git a/day268/problem.go b/day268/problem.go
new file mode 100644
index 0000000..6804bef
--- /dev/null
+++ b/day268/problem.go
@@ -0,0 +1,22 @@
+package day268
+
+// IsPowerFourBrute checks if a number is a power of 4 by repeated
+// division.
+func IsPowerFourBrute(n int32) bool {
+	if n == 0 {
+		return false
+	}
+	for n != 1 {
+		if n%4 != 0 {
+			return false
+		}
+		n /= 4
+	}
+	return true
+}
+
+// IsPowerFourFaster checks if a number is a power of 4
+// by looking for the highest set bits.
+func IsPowerFourFaster(n int32) bool {
+	return n != 0 && ((n & (n - 1)) == 0) && (n&0xAAAAAAA) == 0
+}


Test patch:
diff --git a/day268/problem_test.go b/day268/problem_test.go
new file mode 100644
index 0000000..f1be6b9
--- /dev/null
+++ b/day268/problem_test.go
@@ -0,0 +1,47 @@
+package day268
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	n           int32
+	isPowerFour bool
+}{
+	{16, true},
+	{15, false},
+	{0, false},
+}
+
+func TestIsPowerFourBrute(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := IsPowerFourBrute(tc.n); result != tc.isPowerFour {
+			t.Errorf("For n=%d, expected %v, got %v", tc.n, tc.isPowerFour, result)
+		}
+	}
+}
+
+func BenchmarkIsPowerFourBrute(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			IsPowerFourBrute(tc.n)
+		}
+	}
+}
+
+func TestIsPowerFourFaster(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := IsPowerFourFaster(tc.n); result != tc.isPowerFour {
+			t.Errorf("For n=%d, expected %v, got %v", tc.n, tc.isPowerFour, result)
+		}
+	}
+}
+
+func BenchmarkIsPowerFourFaster(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			IsPowerFourFaster(tc.n)
+		}
+	}
+}