Problem 1668. Josephus Survivor

Created by Richard Zapor

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Josephus_problem\"><w:r><w:t>Josephus Challenge</w:t></w:r></w:hyperlink><w:r><w:t> is to find the position that is the last remaining when every Kth item is removed from a list of N items. The removal wraps from the end to the start.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r><w:r><w:t> N, K where N is the number of players and K is the removal period.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> S the last position remaining</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Example:</w:t></w:r><w:r><w:t> N=4 K=2 produces the sequence</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>1 2 3 4; 1 3 4; 1 3; 1</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Comment:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This is a replication of</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.mathworks.com/matlabcentral/cody/problems/1092-decimation\"><w:r><w:t>Decimation</w:t></w:r></w:hyperlink><w:r><w:t> by James but has a different Historical story reference.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

139 Solutions
34 Solvers

Last Solution submitted on Oct 25, 2022

Last 200 Solutions

Problem Comments

4 Comments

4 Comments

Show 1 older comment

J.R.! Menzinger on 21 Jun 2013

Hi Richard, this problem is the same as this other one: http://www.mathworks.de/matlabcentral/cody/problems/1092-decimation
isn't it??
So I think there is an error on test case number 4 and 5... :-(

andrea84 on 21 Jun 2013

Really like this problem, btw i also got issues with those test cases

James on 21 Jun 2013

I made the Decimation problem referenced above, and I had problems with my test suite as well. Looks like we both would have been standing in the wrong spot in the circle... :-(

Richard Zapor on 21 Jun 2013

I thought I had the right solutions but was unsure. I searched for Josephus to see if this was a duplication, I will look at decimation.

Problem Recent Solvers34

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 1668. Josephus Survivor

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers34

Suggested Problems

More from this Author260

Problem Tags

Community Treasure Hunt

Problem 1668. Josephus Survivor

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers34

Suggested Problems

More from this Author260

Problem Tags

Community Treasure Hunt

Players