Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 225
Good morning! Here's your coding interview problem for today.

This problem was asked by Bloomberg.

There are N prisoners standing in a circle, waiting to be executed. The executions are carried out starting with the kth person, and removing every successive kth person going clockwise until there is no one left.

Given N and k, write an algorithm to determine where a prisoner should stand in order to be the last survivor.

For example, if N = 5 and k = 2, the order of executions would be [2, 4, 1, 5, 3], so you should return 3.

Bonus: Find an O(log N) solution if k = 2.

Pull request description:
Day225
Resolves #465 

Patch:
diff --git a/README.md b/README.md
index 7f50028..3626459 100644
--- a/README.md
+++ b/README.md
@@ -235,3 +235,4 @@ problems from
 * [Day 222](https://github.com/vaskoz/dailycodingproblem-go/issues/458)
 * [Day 223](https://github.com/vaskoz/dailycodingproblem-go/issues/460)
 * [Day 224](https://github.com/vaskoz/dailycodingproblem-go/issues/462)
+* [Day 225](https://github.com/vaskoz/dailycodingproblem-go/issues/465)
diff --git a/day225/problem.go b/day225/problem.go
new file mode 100644
index 0000000..c4a7075
--- /dev/null
+++ b/day225/problem.go
@@ -0,0 +1,25 @@
+package day225
+
+import "math/bits"
+
+// JosephusGeneral is the general case solution.
+func JosephusGeneral(n, k int) int {
+	switch {
+	case n < 1:
+		return 0
+	case n == 1:
+		return 1
+	case k == 2:
+		highestBitValue := 1 << uint(bits.Len64(uint64(n))-1)
+		return 2*(n-highestBitValue) + 1
+	default:
+		return josephusGeneral(n, k) + 1
+	}
+}
+
+func josephusGeneral(n, k int) int {
+	if n == 1 {
+		return 0
+	}
+	return (josephusGeneral(n-1, k) + k) % n
+}


Test patch:
diff --git a/day225/problem_test.go b/day225/problem_test.go
new file mode 100644
index 0000000..44bffba
--- /dev/null
+++ b/day225/problem_test.go
@@ -0,0 +1,31 @@
+package day225
+
+import "testing"
+
+var testcases = []struct {
+	n, k, survivor int
+}{
+	{5, 2, 3},
+	{41, 2, 19},
+	{5, 3, 4},
+	{1, 100, 1},
+	{-20, 100, 0},
+	{0, 100, 0},
+}
+
+func TestJosephusGeneral(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if survivor := JosephusGeneral(tc.n, tc.k); survivor != tc.survivor {
+			t.Errorf("Given N=%d, k=%d, expected %d, got %d", tc.n, tc.k, tc.survivor, survivor)
+		}
+	}
+}
+
+func BenchmarkJosephusGeneral(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			JosephusGeneral(tc.n, tc.k)
+		}
+	}
+}