Last Updated on April 14, 2022 by Ria Pathak
CONCEPTS USED:
Josephus Problem
DIFFICULTY LEVEL:
Hard
PROBLEM STATEMENT(SIMPLIFIED):
Given a circular linked list containing
Nelements from1–Narranged in increasing order and an integerM. 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 Problemrelated 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:
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.
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.
Time Complexityof 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>resultis 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 ) {
head = element ;
head->next = head ;
return head ;
}
while (temp->next != head)
temp = temp->next ;
temp->next = element ;
element->next = head ;
return head ;
}
struct node* ContestWinner(struct node *head, int k, int n)
{
/* if 1 element is only there */
if(n == 1)
return head;
/* 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++){
head = head->next;
}
/* marking its next node as NULL
and returning resultant node address */
head->next = NULL;
return head;
}
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);
head = getNode(head, 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 ;
node *temp = head ;
if ( head == NULL ) {
head = element ;
head->next = head ;
return head ;
}
while (temp->next != head)
temp = temp->next ;
temp->next = element ;
element->next = head ;
return head ;
}
struct node* ContestWinner(struct node *head, int k, int n)
{
/* if 1 element is only there */
if(n == 1)
return head;
/* 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++){
head = head->next;
}
/* marking its next node as NULL
and returning resultant node address */
head->next = NULL;
return head;
}
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;
head = getNode(head, val) ;
}
temp = ContestWinner(head, M, size) ;
if ( temp != NULL )
cout<< temp->value<<endl ;
}
return 0;
}
import java.io.*;
import java.util.*;
public class Main {
static class SinglyLinkedListNode {
public int data;
public SinglyLinkedListNode next;
public SinglyLinkedListNode(int nodeData) {
this.data = nodeData;
this.next = null;
}
}
static class SinglyLinkedList {
public SinglyLinkedListNode head;
public SinglyLinkedListNode tail;
public SinglyLinkedList() {
this.head = null;
this.tail = null;
}
public void insertNode(int nodeData) {
SinglyLinkedListNode node = new SinglyLinkedListNode(nodeData);
if (this.head == null) {
this.head = node;
} else {
this.tail.next = node;
}
this.tail = node;
}
}
static void printLinkedList(SinglyLinkedListNode head) {
SinglyLinkedListNode temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
static SinglyLinkedListNode ContestWinner(SinglyLinkedListNode head, int k, int n)
{
/* if 1 element is only there */
if(n == 1)
return head;
/* 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++){
head = head.next;
}
/* marking its next node as NULL
and returning resultant node address */
head.next = null;
return head;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
int testCases = scanner.nextInt();
while (testCases-- > 0) {
SinglyLinkedList llist = new SinglyLinkedList();
int size = scanner.nextInt();
int M = scanner.nextInt();
for (int i = 0; i < size; i++) {
int llistItem = scanner.nextInt();
llist.insertNode(llistItem);
}
SinglyLinkedListNode temp = ContestWinner(llist.head, M, size);
System.out.println(temp.data);
}
}
}
Space Complexity: O(1)
[forminator_quiz id="2129"]
This article tried to discuss Josephus Problem. Hope this blog helps you understand the concept. To practice more problems you can check out MYCODE | Competitive Programming