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
Similar Kata:
Stats:
Created | May 15, 2015 |
Published | May 15, 2015 |
Warriors Trained | 50990 |
Total Skips | 11362 |
Total Code Submissions | 66646 |
Total Times Completed | 16695 |
Python Completions | 4198 |
JavaScript Completions | 3093 |
Ruby Completions | 481 |
Java Completions | 2645 |
CoffeeScript Completions | 25 |
Haskell Completions | 195 |
C# Completions | 1302 |
Elixir Completions | 121 |
PHP Completions | 463 |
Go Completions | 541 |
Clojure Completions | 33 |
TypeScript Completions | 569 |
C++ Completions | 1290 |
Crystal Completions | 19 |
Dart Completions | 321 |
Julia Completions | 41 |
R Completions | 68 |
Reason Completions | 4 |
Factor Completions | 13 |
Elm Completions | 18 |
Objective-C Completions | 10 |
Lua Completions | 89 |
F# Completions | 43 |
Swift Completions | 261 |
Rust Completions | 417 |
Forth Completions | 11 |
Groovy Completions | 28 |
C Completions | 537 |
Kotlin Completions | 359 |
Nim Completions | 20 |
Scala Completions | 147 |
Racket Completions | 19 |
PureScript Completions | 15 |
PowerShell Completions | 26 |
Fortran Completions | 13 |
VB Completions | 21 |
Erlang Completions | 47 |
Shell Completions | 22 |
NASM Completions | 14 |
CFML Completions | 10 |
Prolog Completions | 17 |
OCaml Completions | 28 |
Haxe Completions | 13 |
COBOL Completions | 12 |
Total Stars | 1204 |
% of votes with a positive feedback rating | 89% of 1635 |
Total "Very Satisfied" Votes | 1324 |
Total "Somewhat Satisfied" Votes | 257 |
Total "Not Satisfied" Votes | 54 |