Contest Winner

CONCEPTS USED:

Josephus Problem

DIFFICULTY LEVEL:

Hard

PROBLEM STATEMENT(SIMPLIFIED):

Given a circular linked list containing N elements from 1N 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 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 ) {
        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)
{
    node *temp = head;

    /* finding the previous node of head */
    while(temp->next != head){
      temp = temp->next;
    }

    node *it = head;
    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);
            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)
{
    node *temp = head;

    /* finding the previous node of head */
    while(temp->next != head){
      temp = temp->next;
    }

    node *it = head;
    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;
            head = getNode(head, val) ;
        }
        temp = ContestWinner(head, M, size) ;
        if ( temp != NULL )
            cout<< temp->value<<endl ;
    }
    return 0;
}

EFFICIENT METHOD:

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 ) {
        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)

Previous post Binary list
Next post Arrange the Salary

Leave a Reply

Your email address will not be published. Required fields are marked *