  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Contest Winner

Last Updated on April 14, 2022 by Ria Pathak 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.

### SOLVING APPROACH:

#### 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.

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(N2)```.</p> </li> </ol> </blockquote> <h3>SOLUTIONS:</h3> <p>[TABS_R id=2035]</p> <h4>EFFICIENT METHOD:</h4> <p><strong>OBSERVATION</strong>:</p> <p>Taking few different values of <code>n</code> and <code>k</code>, we can construct the following table :</p> <table> <thead> <tr> <th>n/k</th> <th>1</th> <th>2</th> <th>3</th> <th>4</th> <th>5</th> <th>6</th> <th>7</th> <th>8</th> <th>9</th> <th>10</th> </tr> </thead> <tbody> <tr> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> <td>1</td> </tr> <tr> <td>2</td> <td>2</td> <td>1</td> <td>2</td> <td>1</td> <td>2</td> <td>1</td> <td>2</td> <td>1</td> <td>2</td> <td>1</td> </tr> <tr> <td>3</td> <td>3</td> <td>3</td> <td>2</td> <td>2</td> <td>1</td> <td>1</td> <td>3</td> <td>3</td> <td>2</td> <td>2</td> </tr> <tr> <td>4</td> <td>4</td> <td>1</td> <td>1</td> <td>2</td> <td>2</td> <td>3</td> <td>2</td> <td>3</td> <td>3</td> <td>4</td> </tr> <tr> <td>5</td> <td>5</td> <td>3</td> <td>4</td> <td>1</td> <td>2</td> <td>4</td> <td>4</td> <td>1</td> <td>2</td> <td>4</td> </tr> <tr> <td>6</td> <td>6</td> <td>5</td> <td>1</td> <td>5</td> <td>1</td> <td>4</td> <td>5</td> <td>3</td> <td>5</td> <td>2</td> </tr> <tr> <td>7</td> <td>7</td> <td>7</td> <td>4</td> <td>2</td> <td>6</td> <td>3</td> <td>5</td> <td>4</td> <td>7</td> <td>5</td> </tr> <tr> <td>8</td> <td>8</td> <td>1</td> <td>7</td> <td>6</td> <td>3</td> <td>1</td> <td>4</td> <td>4</td> <td>8</td> <td>7</td> </tr> <tr> <td>9</td> <td>9</td> <td>3</td> <td>1</td> <td>1</td> <td>8</td> <td>7</td> <td>2</td> <td>3</td> <td>8</td> <td>8</td> </tr> <tr> <td>10</td> <td>10</td> <td>5</td> <td>4</td> <td>5</td> <td>3</td> <td>3</td> <td>9</td> <td>1</td> <td>7</td> <td>8</td> </tr> </tbody> </table> <pre><code>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.</code></pre> <blockquote> <ol> <li> <p>Now we can easily find the solution of <code>Josephus(n, k)</code> with the help of <code>Josephus(n - 1, k)</code>.</p> </li> <li> <p>For this simply run a loop till <code>n</code> and keep calculating -<br /> <code>result = (result + k-1) % i + 1</code><br /> where <code>(1 <= i 3. This </code>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);
}
Space Complexity: `O(1)`