Last active
December 24, 2015 15:09
-
-
Save cciollaro/6817577 to your computer and use it in GitHub Desktop.
Survivor Solution in Java using Recursion
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//There are 100 people sat at a circular table. | |
//You go around the table asking every second person to leave (starting by asking the guy at seat 1 to leave) until there is one person left. | |
//Which seat is left? | |
//usage: java Survivor 100 | |
class Survivor { | |
public static void main(String[] args){ | |
int n = Integer.parseInt(args[0]); | |
int result = eliminate(1, 1, n, false); | |
System.out.println(result); | |
} | |
public static int eliminate(int distance, int first, int n, boolean safe){ | |
if(n == 1) | |
return first; | |
int new_first = (safe ? first : first + distance); //if safe is not true then the person at first is eliminated and the new first becomes first + distance. | |
int new_n = (n%2==1 && safe ? n/2 + 1 : n/2); //if n is odd and the first person is safe, then n/2 + 1 people remain. | |
boolean new_safe = (n%2==1 ? !safe : safe); //if n is odd then the safety of the first person next round will flip | |
return eliminate(distance*2, new_first, new_n, new_safe); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment