Algorithms/JosephusProblem.java at master · AaryanShaikh/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/* n people (numbered 1 to n) are standing in a circle. Person 1 kills person 2 with a sword/knife and
gives it to person 3. person 3 kills person 4 with sword/knife and gives it to person 5. this process
is repeated until only one person is alive.
(medium) -> given the number of people N, write a program to find the person that stays alive at the
end.
(Hard) -> Show each step of the process.
*/
import java.util.*;
public class JosephusProblem{
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int arr[] = new int[n];
		Arrays.fill(arr,0);
		int i=0,count=0;
		boolean once = true;
		while(true){
			if (arr[i]==0) {
				int k=(i+1)%n;
				while(arr[k%n]!=0){
					k=(k+1)%n;
				}
				if (arr[k%n]==0) {
					boolean ch = ((k+1)!=n)?true:false;
					if (ch) {
						boolean ch2 = ((i+1)!=n)?true:false;
						if (ch2) {
							if (once) {
								System.out.print((i+1)%n+" will kill "+(k+1)%n);
								once = false;
							}else{
								System.out.print((i+1)%n+"\n"+(i+1)%n+" will kill "+(k+1)%n);
							}
							boolean ch3 = ((k+2)!=n)?true:false;
							if (ch3) {
								System.out.print(" and will give the knife to ");
							}else{
								System.out.print(" and will give the knife to ");
							}
						}else{
							System.out.print(n+" will kill "+(k+1)%n);
							boolean ch3 = ((k+2)!=n)?true:false;
							if (ch3) {
								System.out.print(" and will give the knife to ");
							}else{
								System.out.print(" and will give the knife to ");
							}
						}
					}else{
						boolean ch2 = ((i+1)!=n)?true:false;
						if (ch2) {
							System.out.print((i+1)%n+" will kill "+n);
							boolean ch3 = ((k+2)!=n)?true:false;
							if (ch3) {
								System.out.print(" and will give the knife to ");
							}else{
								System.out.print(" and will give the knife to ");
							}
						}else{
							System.out.print(n+" will kill "+n);
							boolean ch3 = ((k+2)!=n)?true:false;
							if (ch3) {
								System.out.print(" and will give the knife to ");
							}else{
								System.out.print(" and will give the knife to ");
							}
						}
					}
					arr[k%n] = 1;
				}
			}
			count=0;
			for (int j=0;j<n ;j++ ) {
				if (arr[j]==0) {
					count++;
				}
			}
			if (count==1) {
				break;
			}
			i=(i+1)%n;
		}
		for (int j=0;j<n ;j++ ) {
			if (arr[j]==0) {
				System.out.println((j+1)+"\n"+(j+1)+" survived!");
				break;
			}
		}
	}
}