I've been trying to program the Josephus problem and for some reason it is only working in some situations, I'm unsure why. The TL;DR of how it works is this:
You have X group of people in a circle. Every Nth person is going to be killed until only one final person remains. So say for example you have 10[AKA: X] people and you decide to kill every 3rd [AKA: Nth] person it will look like this:
1st round: 1, 2, (3 dies), 4, 5, (6 dies), 7, 8, (9 dies), 10
2nd round: 1, (2 dies because it is a continuous circle), 3, 5, (7 dies), 8, 10
3rd round: (1), 4, 5, (8), 10
4th round: 4, (5), 10
5th round: 4, (10)
And we are finally left with person #4 as the lone survivor.
My program does this perfectly fine. However, when I enter X as 55
and N as 17
I get the incorrect answer of person 27
when it should be person 40
. Can anyone tell me where my loop messes up?
Source code:
def solveJosephus(specifics):
people = [int(x) for x in range(1,int(specifics[0])+1)]
killPosition = int(specifics[1])
positionCounter = 0
sorted = False
while not sorted:
if len(people) == 1:
print(people[0]) # Pyschologically scarred Winner!
sorted = True
for person in people:
positionCounter += 1
if positionCounter == killPosition:
print(person)
people.remove(person)
positionCounter = 1
solveJosephus(raw_input().split())
The problem is you are removing people from the list while iterating through it.
What happens is the following:
Say you have X = 5
and N = 2
. Your list is [1,2,3,4,5]
. You get to index = 1
and person 2 dies. Now your list is [1,3,4,5]
. The problem is your index still equals 1
but now that points to person 3. When you go two more places (index = 3), instead of killing person 4, you kill person 5.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With