Repository: TheAlgorithms/Java
Pull request #3208 (2022-08-06 06:07:50)

Add Josephus Problem Recursive Solution
### **Describe your change:**
Fixes: #3207 

- [x] Add an algorithm?
- [ ] Fix a bug or typo in an existing algorithm?
- [ ] Documentation change?

#### References

https://en.wikipedia.org/wiki/Josephus_problem
<!-- Add any reference to previous pull-request or issue -->

### **Checklist:**

<!-- Remove items that do not apply. For completed items, change [ ] to [x]. -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized.
- [x] I know that pull requests will not be merged if they fail the automated tests.
- [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
- [x] All new Java files are placed inside an existing directory.
- [x] All filenames are in all uppercase characters with no spaces or dashes.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation.
- [x] If this pull request resolves one or more open issues then the commit message contains `Fixes: #{$ISSUE_NO}`.


Kunal0007: > The code looks good, could you please add some automated tests? (see https://github.com/TheAlgorithms/Java/tree/master/src/test/java/com/thealgorithms)

Sure, added JosephusProblemTest.java

Patch:
diff --git a/src/main/java/com/thealgorithms/maths/JosephusProblem.java b/src/main/java/com/thealgorithms/maths/JosephusProblem.java
new file mode 100644
index 00000000..f2f14b90
--- /dev/null
+++ b/src/main/java/com/thealgorithms/maths/JosephusProblem.java
@@ -0,0 +1,36 @@
+package com.thealgorithms.maths;
+
+     /** There are n friends that are playing a game. The friends are sitting in a circle and are    numbered from 1 to n in clockwise order. More formally, moving clockwise from the ith friend brings you to the (i+1)th friend for 1 <= i < n, and moving clockwise from the nth friend brings you to the 1st friend.
+    */
+
+    /** The rules of the game are as follows:
+
+        1.Start at the 1st friend.
+        2.Count the next k friends in the clockwise direction including the friend you started at. The counting wraps around the circle and may count some friends more than once.
+        3.The last friend you counted leaves the circle and loses the game.
+        4.If there is still more than one friend in the circle, go back to step 2 starting from the friend immediately clockwise of the friend who just lost and repeat.
+        5.Else, the last friend in the circle wins the game.
+
+        @author Kunal
+    */
+
+public class JosephusProblem {
+
+    /**
+     * Find the Winner of the Circular Game.
+     *
+     * @param number of friends, n, and an integer k
+     * @return return the winner of the game
+     */
+
+    public static int findTheWinner(int n, int k) {
+        return winner(n, k) + 1;
+    }
+    
+    public static int winner(int n, int k){
+        if (n == 1){
+            return 0;
+        }
+        return (winner(n -1, k) + k) % n;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/maths/JosephusProblemTest.java b/src/test/java/com/thealgorithms/maths/JosephusProblemTest.java
new file mode 100644
index 00000000..66f091c1
--- /dev/null
+++ b/src/test/java/com/thealgorithms/maths/JosephusProblemTest.java
@@ -0,0 +1,15 @@
+package com.thealgorithms.maths;
+
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+public class JosephusProblemTest {
+
+    @Test
+    void testJosephusProblem(){
+        assertEquals(3, JosephusProblem.findTheWinner(5,2));
+        assertEquals(5, JosephusProblem.findTheWinner(6,4));
+    }
+
+}