5 kyu

Josephus Survivor

4,198 of 16,695GiacomoSorbi

Description:

In this kata you have to correctly return who is the "survivor", ie: the last element of a Josephus permutation.

Basically you have to assume that n people are put into a circle and that they are eliminated in steps of k elements, like this:

n=7, k=3 => means 7 people in a circle
one every 3 is eliminated until one remains
[1,2,3,4,5,6,7] - initial sequence
[1,2,4,5,6,7] => 3 is counted out
[1,2,4,5,7] => 6 is counted out
[1,4,5,7] => 2 is counted out
[1,4,5] => 7 is counted out
[1,4] => 5 is counted out
[4] => 1 counted out, 4 is the last element - the survivor!

The above link about the "base" kata description will give you a more thorough insight about the origin of this kind of permutation, but basically that's all that there is to know to solve this kata.

Notes and tips: using the solution to the other kata to check your function may be helpful, but as much larger numbers will be used, using an array/list to compute the number of the survivor may be too slow; you may assume that both n and k will always be >=1.

Mathematics
Combinatorics
Algorithms
Lists
Arrays

Stats:

CreatedMay 15, 2015
PublishedMay 15, 2015
Warriors Trained50990
Total Skips11362
Total Code Submissions66646
Total Times Completed16695
Python Completions4198
JavaScript Completions3093
Ruby Completions481
Java Completions2645
CoffeeScript Completions25
Haskell Completions195
C# Completions1302
Elixir Completions121
PHP Completions463
Go Completions541
Clojure Completions33
TypeScript Completions569
C++ Completions1290
Crystal Completions19
Dart Completions321
Julia Completions41
R Completions68
Reason Completions4
Factor Completions13
Elm Completions18
Objective-C Completions10
Lua Completions89
F# Completions43
Swift Completions261
Rust Completions417
Forth Completions11
Groovy Completions28
C Completions537
Kotlin Completions359
Nim Completions20
Scala Completions147
Racket Completions19
PureScript Completions15
PowerShell Completions26
Fortran Completions13
VB Completions21
Erlang Completions47
Shell Completions22
NASM Completions14
CFML Completions10
Prolog Completions17
OCaml Completions28
Haxe Completions13
COBOL Completions12
Total Stars1204
% of votes with a positive feedback rating89% of 1635
Total "Very Satisfied" Votes1324
Total "Somewhat Satisfied" Votes257
Total "Not Satisfied" Votes54
Ad
Contributors
  • GiacomoSorbi Avatar
  • dnolan Avatar
  • hencethus Avatar
  • g964 Avatar
  • AngusJGoldsmith Avatar
  • donaldsebleung Avatar
  • imjasonmiller Avatar
  • kazk Avatar
  • Voile Avatar
  • Helge801 Avatar
  • monadius Avatar
  • hobovsky Avatar
  • user8436785 Avatar
  • el-f Avatar
  • akar-0 Avatar
  • Just4FunCoder Avatar
Ad