Skip to content

Instantly share code, notes, and snippets.

@cciollaro
Last active December 24, 2015 15:09
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save cciollaro/6817577 to your computer and use it in GitHub Desktop.
Save cciollaro/6817577 to your computer and use it in GitHub Desktop.
Survivor Solution in Java using Recursion
//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