{"id":8144,"date":"2022-04-14T14:34:23","date_gmt":"2022-04-14T14:34:23","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=8144"},"modified":"2022-04-14T14:37:26","modified_gmt":"2022-04-14T14:37:26","slug":"contest-winner","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/contest-winner\/","title":{"rendered":"Contest Winner"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Josephus Problem<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Hard <\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Given a circular linked list containing N<\/code> elements from 1<\/code> – N<\/code> arranged in increasing order and an integer M<\/code>. Your task is to keep eliminating Mth<\/sup> element from the list, starting from the beginning till only one element is left in the list.<\/p>\n

NOTE<\/em><\/strong> : First, eliminates the Mth<\/sup> element from the beginning, then again start eliminating from (M+1)th<\/sup> element. <\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example:<\/h4>\n
Input : \n\nN = 5, K = 3\nlist = 1 -> 2 -> 3 -> 4 -> 5\n\nOutput : 4\n\nExplanation : \n\nThe 3rd element from the starting position is 3 which is removed first, 4 becomes new starting position\n\n1 -> 2 -> 4 -> 5\n\nThen the 3rd element from position 4 i.e. 1 is removed, 2 becomes new starting position\n\n2 -> 4 -> 5\n\nThen 3rd element from position 2 i.e. 5 is removed, 2 again becomes new starting position\n\n2 -> 4\n\nThen 3rd element from position 2 i.e. 2 itself is removed\n\n4 is the single element left and is the resultant element.<\/code><\/pre>\n
Do you Know ?<\/em><\/strong><\/p>\n
\n
This is a popular problem known as Josephus Problem<\/code> related to a certain counting-out game.
\nPeople 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.<\/p>\n<\/blockquote>\n
SOLVING APPROACH:<\/h3>\n
BRUTE FORCE METHOD:<\/h4>\n
\n
    \n
  1. \n
    The idea is to simply move the head pointer of the linked list by K<\/strong> steps and and removing the Kth<\/sup><\/strong> node, by assigning the (K+1)th<\/sup><\/strong> node address to the next<\/strong> pointer of (K-1)th<\/sup><\/strong> node.    <\/p>\n<\/li>\n
  2. \n
    Now considering (K+1)th<\/sup><\/strong> node as our new head<\/code>, keep following the same procedure till a single element is left in the linked list.<\/p>\n<\/li>\n
  3. \n
    Time Complexity<\/code> of this solution is O(N2<\/sup>)<\/strong>`.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
    SOLUTIONS:<\/h3>\n\t\t\t\t\t\t