How to solve the Josephus Problem?

Do you like puzzles and mathematical problems? Then, get ready to play the Josephus game! It's a game of survival where the winner is the last person standing.

[{"selector":"#anim-6d58e727-4be8-4300-a525-9c00bd15751d","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-558af353-38b5-489d-bd79-1c5f51695a3b","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-22f0874d-25c3-41f6-9dcc-f8a1ee55c4e4 [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Click here

Consider N people standing in a circle. Every K-th person is eliminated until only one person remains. The task is to find the last person.

[{"selector":"#anim-f647ba22-e78d-4beb-9287-033100a47fad [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-802bded1-a355-4a32-991b-23a9b48061d8","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-3428c952-045f-4672-824c-3ba7c7b79fdf","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-45bf76b5-52eb-44df-88ac-8cdbcf759e20","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-fa439f86-8602-4ab9-ba77-14e6a0e0f095","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Click here

We use a recursive function that calculates the position of the survivor in a circle of N people, with every K-th person being eliminated.

[{"selector":"#anim-d8eb9b44-b153-4748-9ea0-9d3cdb7d4d5c","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-238afe0e-991d-4184-ae3e-3a790710ba6d","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-86f36795-4e33-406b-b739-6130cd4cfc01 [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-9fd5510a-d5e7-4202-9185-e01934ac6f0c","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-58506074-3b26-47e8-978c-6eb89148a3db","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Click here

Algorithm - 1. Step 1: If N == 1, return 1. 2. Step 2: Else, return (josephus(N – 1 , K) + K – 1) % N + 1. Curious to see it in action?

[{"selector":"#anim-4264c0e2-cccb-4c68-8698-578ee28ef04c [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-31662719-7573-4d8c-a64e-0f6fc8ddaf93","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-23551c5d-f8e7-417c-94a0-2b2f1a533805","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Click here

Simplify the Josephus problem with a list approach! Initialize a list of integers from 1 to N, then repeatedly remove the K-th element until only one remains.

[{"selector":"#anim-707e39f0-b02b-49ae-b7bf-3be5581e2c5c [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-ba6ae408-a224-422f-9d18-94fb35c3cfed","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-86b9b1ad-e2ac-4873-a1a0-5e172b32b902","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-09d70def-1d52-4161-8d58-58e47054fded","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-84cd824f-29d6-45c9-9c6f-d1c03bc63db2","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Click here

If N is even, all even positions get deleted leaving N/2. The solution? josephus(2 * N, 2) = josephus(N, 2) - 1 And for N odd? Find out by clicking here!

[{"selector":"#anim-7de70feb-1f98-494d-9839-f7a14e25f022","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-0dac2785-a2bc-49f2-b3f0-85a5bb6615d8","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-a300fb75-1d44-4913-8236-a9c89ed3a82e [data-leaf-element=\"true\"]","keyframes":{"transform":["translate(0%, 0%) scale(1.5)","translate(0%, 0%) scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] [{"selector":"#anim-229a6b85-2bb2-4454-858c-9bde41624be2","keyframes":{"opacity":[0,1]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"both"}] [{"selector":"#anim-c8430741-9748-495f-a3a3-d032a5e894c7","keyframes":{"transform":["scale(0.3333333333333333)","scale(1)"]},"delay":0,"duration":2000,"easing":"cubic-bezier(.3,0,.55,1)","fill":"forwards"}] Click here

Click on the link below to start your journey.

[{"selector":"#anim-db71851c-7c7a-4367-9073-bf187d1a3eec","keyframes":{"opacity":[0,1]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-afc23b4e-29b0-4816-962f-5642ee86abfd","keyframes":{"transform":["translate3d(-111.74377%, 0px, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-f6a72e0e-7001-4896-965a-b155e8f5f0e2","keyframes":{"opacity":[0,1]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-b2594a01-af20-418f-ad86-0c3e9a6d9d8e","keyframes":{"transform":["translate3d(0px, -329.05351%, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] Click here

Don't miss out on the chance to upskill yourself with IntervewBit's engaging web stories.

[{"selector":"#anim-77c84162-1024-4d3e-be06-850d08359f89","keyframes":{"opacity":[0,1]},"delay":0,"duration":1000,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-a3170365-00ac-4437-bbf5-7f0ead509420","keyframes":{"transform":["translate3d(0px, -211.49618%, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":1000,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-be1c6531-0f42-494e-a23f-fdff1826d9c0","keyframes":{"opacity":[0,1]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] [{"selector":"#anim-d728833e-84e8-4333-96ae-192e80b1cf03","keyframes":{"transform":["translate3d(0px, -621.00265%, 0)","translate3d(0px, 0px, 0)"]},"delay":0,"duration":600,"easing":"cubic-bezier(0.2, 0.6, 0.0, 1)","fill":"both"}] Step Up Your Game with InterviewBit Web Stories SWIPE UP

How to solve the Josephus Problem?

A Puzzling Survival Game

Do you like puzzles and mathematical problems? Then, get ready to play the Josephus game! It's a game of survival where the winner is the last person standing.

Consider N people standing in a circle. Every K-th person is eliminated until only one person remains. The task is to find the last person.

Problem Statement

We use a recursive function that calculates the position of the survivor in a circle of N people, with every K-th person being eliminated.

Approach 1- Recursive Approach

Algorithm - 1. Step 1: If N == 1, return 1. 2. Step 2: Else, return (josephus(N – 1 , K) + K – 1) % N + 1. Curious to see it in action?

Simplify the Josephus problem with a list approach! Initialize a list of integers from 1 to N, then repeatedly remove the K-th element until only one remains.

Approach 2- List Method

If N is even, all even positions get deleted leaving N/2. The solution? josephus(2 * N, 2) = josephus(N, 2) - 1 And for N odd? Find out by clicking here!

Special Case: K=2 A Game Changer!

Click on the link below to start your journey.

Are you ready to up your coding game?

Don't miss out on the chance to upskill yourself with IntervewBit's engaging web stories.

“