# Contest Winner

Josephus Problem

Hard

#### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given a circular linked list containing `N` elements from `1` - `N` arranged in increasing order and an integer `M`. Your task is to keep eliminating `Mth` element from the list, starting from the beginning till only one element is left in the list.

NOTE : First, eliminates the `Mth` element from the beginning, then again start eliminating from `(M+1)th` element.

See original problem statement here

#### For Example:

``````Input :

N = 5, K = 3
list = 1 -> 2 -> 3 -> 4 -> 5

Output : 4

Explanation :

The 3rd element from the starting position is 3 which is removed first, 4 becomes new starting position

1 -> 2 -> 4 -> 5

Then the 3rd element from position 4 i.e. 1 is removed, 2 becomes new starting position

2 -> 4 -> 5

Then 3rd element from position 2 i.e. 5 is removed, 2 again becomes new starting position

2 -> 4

Then 3rd element from position 2 i.e. 2 itself is removed

4 is the single element left and is the resultant element.``````

Do you Know ?

This is a popular problem known as `Josephus Problem` related to a certain counting-out game.
People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed.

#### BRUTE FORCE METHOD:

1. The idea is to simply move the `head` pointer of the linked list by `K` steps and and removing the `Kth` node, by assigning the `(K+1)th` node address to the `next` pointer of `(K-1)th` node referring a html online course.

2. Now considering `(K+1)th` node as our new `head`, keep following the same procedure till a single element is left in the linked list.

3. `Time Complexity` of this solution is `O(N^2)`.

#### SOLUTIONS:

```
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int value;
struct node* next;
}node;

struct node* getNode (struct node *head, int val)
{
struct node *element = (struct node*) malloc(sizeof(struct node));
element->value = val ;
element->next = NULL ;
struct node *temp = head ;
if ( head == NULL ) {
}
temp = temp->next ;
temp->next = element ;
}

struct node* ContestWinner(struct node *head, int k, int n)
{

/* finding the previous node of head */
temp = temp->next;
}

node *prev = temp;
while(n)
{
/* if only 1 element is left return it*/
if(n == 1)
{
return it;
break;
}
int size = n;
int kk;
if(k > size){
if(k%size == 0){
kk = size;
}
else{
kk = k%size;
}
}
else
kk = k;

/* increment steps by k to reach the node to be deleted */
for(int i=0;i<kk-1;i++){
prev = it;
it = it->next;
}
/* delete the node by making its previous node point to its next node */
prev->next = it->next;
it = prev->next;

/* decrement the count of nodes */
n--;

}
}

int main() {
int t;
scanf("%d",&t);
while(t--){
struct node *head = NULL, *temp ;
int size, i, val, M;

scanf("%d %d",&size, &M);

for ( i = 0 ; i < size ; i ++ ) {
scanf("%d",&val);
}
temp = ContestWinner(head, M, size) ;
if ( temp != NULL )
printf("%d\n", temp->value) ;
}
return 0;
}
```
```
#include <bits/stdc++.h>
using namespace std;
typedef struct node
{
int value;
struct node* next;
}node;

node* getNode (node *head, int val)
{
node *element = new node;
element->value = val ;
element->next = NULL ;
if ( head == NULL ) {
}
temp = temp->next ;
temp->next = element ;
}

struct node* ContestWinner(struct node *head, int k, int n)
{

/* finding the previous node of head */
temp = temp->next;
}

node *prev = temp;
while(n)
{
/* if only 1 element is left return it*/
if(n == 1)
{
return it;
}
int size = n;
int kk;
if(k > size){
if(k%size == 0){
kk = size;
}
else{
kk = k%size;
}
}
else
kk = k;

/* increment steps by k to reach the node to be deleted */
for(int i=0;i<kk-1;i++){
prev = it;
it = it->next;
}
/* delete the node by making its previous node point to its next node */
prev->next = it->next;
it = prev->next;

/* decrement the count of nodes */
n--;

}
}

int main() {
int t;
cin>>t;
while(t--){
node *head = NULL, *temp ;
int size, i, val, M;

cin>>size>>M;

for ( i = 0 ; i < size ; i ++ ) {
cin>>val;
}
temp = ContestWinner(head, M, size) ;
if ( temp != NULL )
cout<< temp->value<<endl ;
}
return 0;
}
```

#### OBSERVATION:

Taking few different values of `n` and `k`, we can construct the following table :

n/k 1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1 1
2 2 1 2 1 2 1 2 1 2 1
3 3 3 2 2 1 1 3 3 2 2
4 4 1 1 2 2 3 2 3 3 4
5 5 3 4 1 2 4 4 1 2 4
6 6 5 1 5 1 4 5 3 5 2
7 7 7 4 2 6 3 5 4 7 5
8 8 1 7 6 3 1 4 4 8 7
9 9 3 1 1 8 7 2 3 8 8
10 10 5 4 5 3 3 9 1 7 8
``````With the help of the above table we can observe that the problem has below Recursive Structure :-

Josephus(n, k) = (Josephus(n - 1, k) + k-1) % n + 1

Josephus(1, k) = 1

As for any value of k, if the number of elements is 1, then it will be our answer.``````
1. Now we can easily find the solution of `Josephus(n, k)` with the help of `Josephus(n - 1, k)`.

2. For this simply run a loop till `n` and keep calculating -
`result = (result + k-1) % i + 1`
where `(1 <= i 3. This `result` is the element that will remain till the end.

#### SOLUTIONS:

```
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int value;
struct node* next;
}node;

struct node* getNode (struct node *head, int val)
{
struct node *element = (struct node*) malloc(sizeof(struct node));
element->value = val ;
element->next = NULL ;
struct node *temp = head ;
if ( head == NULL ) {
}
temp = temp->next ;
temp->next = element ;
}

struct node* ContestWinner(struct node *head, int k, int n)
{
/* if 1 element is only there */
if(n == 1)

/* for storing our resultant element */
int res = 0;

for(int i=1; i<=n; i++){
res = (res + k-1)%i + 1;
}

/* finding the node of resultant element */
for(int i=1; i<res; i++){
}

/* marking its next node as NULL
and returning resultant node address */
}

int main() {
int t;
scanf("%d",&t);
while(t--){
struct node *head = NULL, *temp ;
int size, i, val, M;

scanf("%d %d",&size, &M);

for ( i = 0 ; i < size ; i ++ ) {
scanf("%d",&val);
}
temp = ContestWinner(head, M, size) ;
if ( temp != NULL )
printf("%d\n", temp->value) ;
}
return 0;
}
```
```
#include <bits/stdc++.h>
using namespace std;
typedef struct node
{
int value;
struct node* next;
}node;

node* getNode (node *head, int val)
{
node *element = new node;
element->value = val ;
element->next = NULL ;
if ( head == NULL ) {
}
temp = temp->next ;
temp->next = element ;
}

struct node* ContestWinner(struct node *head, int k, int n)
{
/* if 1 element is only there */
if(n == 1)

/* for storing our resultant element */
int res = 0;

for(int i=1; i<=n; i++){
res = (res + k-1)%i + 1;
}

/* finding the node of resultant element */
for(int i=1; i<res; i++){
}

/* marking its next node as NULL
and returning resultant node address */
}

int main() {
int t;
cin>>t;
while(t--){
node *head = NULL, *temp ;
int size, i, val, M;

cin>>size>>M;

for ( i = 0 ; i < size ; i ++ ) {
cin>>val;
}
temp = ContestWinner(head, M, size) ;
if ( temp != NULL )
cout<< temp->value<<endl ;
}
return 0;
}
```
```
import java.io.*;
import java.util.*;

public class Main {

public int data;

this.data = nodeData;
this.next = null;
}
}

this.tail = null;
}

public void insertNode(int nodeData) {

} else {
this.tail.next = node;
}

this.tail = node;
}
}

while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}

{
/* if 1 element is only there */
if(n == 1)

/* for storing our resultant element */
int res = 0;

for(int i=1; i<=n; i++){
res = (res + k-1)%i + 1;
}

/* finding the node of resultant element */
for(int i=1; i<res; i++){
}

/* marking its next node as NULL
and returning resultant node address */
}
private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
int testCases = scanner.nextInt();
while (testCases-- > 0) {
int size = scanner.nextInt();
int M = scanner.nextInt();
for (int i = 0; i < size; i++) {
int llistItem = scanner.nextInt();
llist.insertNode(llistItem);
}