Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 217
Good morning! Here's your coding interview problem for today.

This problem was asked by Oracle.

We say a number is sparse if there are no adjacent ones in its binary representation. For example, 21 (10101) is sparse, but 22 (10110) is not. For a given input N, find the smallest sparse number greater than or equal to N.

Do this in faster than O(N log N) time.

Pull request description:
Day217
Resolves #447.

Patch:
diff --git a/README.md b/README.md
index b9f072f..8e47b1a 100644
--- a/README.md
+++ b/README.md
@@ -227,3 +227,4 @@ problems from
 * [Day 214](https://github.com/vaskoz/dailycodingproblem-go/issues/441)
 * [Day 215](https://github.com/vaskoz/dailycodingproblem-go/issues/443)
 * [Day 216](https://github.com/vaskoz/dailycodingproblem-go/issues/445)
+* [Day 217](https://github.com/vaskoz/dailycodingproblem-go/issues/447)
diff --git a/day217/problem.go b/day217/problem.go
new file mode 100644
index 0000000..17c0288
--- /dev/null
+++ b/day217/problem.go
@@ -0,0 +1,37 @@
+package day217
+
+// SmallestSparseNumberGreaterThan returns the smallest
+// number with no adjacent 1's in the binary form.
+// If n is already sparse, it returns n.
+// Runs in O(num of bits)
+func SmallestSparseNumberGreaterThan(n uint) uint {
+	if n < 3 {
+		return n
+	}
+	var result uint
+	var bits, ones int
+	for n != 0 {
+		bit := n & 1
+		n >>= 1
+		if bit == 1 {
+			ones++
+		} else {
+			if ones > 1 {
+				n <<= 1
+				n |= 1
+				result = 1 << uint(bits)
+				bits--
+			} else {
+				result |= 1 << uint(bits-1)
+			}
+			ones = 0
+		}
+		bits++
+	}
+	if ones == 1 {
+		result |= 1 << uint(bits-1)
+	} else if ones > 1 {
+		result = 1 << uint(bits)
+	}
+	return result
+}


Test patch:
diff --git a/day217/problem_test.go b/day217/problem_test.go
new file mode 100644
index 0000000..a6df56d
--- /dev/null
+++ b/day217/problem_test.go
@@ -0,0 +1,31 @@
+package day217
+
+import "testing"
+
+var testcases = []struct {
+	n, expected uint
+}{
+	{21, 21},
+	{22, 32},
+	{0, 0},
+	{1, 1},
+	{2, 2},
+	{3, 4},
+}
+
+func TestSmallestSparseNumberGreaterThan(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := SmallestSparseNumberGreaterThan(tc.n); result != tc.expected {
+			t.Errorf("For N=%v, expected %v, got %v", tc.n, tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkSmallestSparseNumberGreaterThan(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			SmallestSparseNumberGreaterThan(tc.n)
+		}
+	}
+}