{"id":2888,"date":"2023-08-18T18:09:08","date_gmt":"2023-08-18T12:39:08","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2888"},"modified":"2023-08-18T18:09:10","modified_gmt":"2023-08-18T12:39:10","slug":"josephus-problem","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/josephus-problem\/","title":{"rendered":"Josephus Problem"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#recursive-approach\">Recursive Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#using-list---approach-2\">Using List &#8211; Approach 2<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#special-case-k--2\">Special Case: K = 2<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#practice-question\">Practice Question<\/a><\/li><li><a href=\"#faqs\">FAQs<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-what-data-structure-is-used-in-solving-the-josephus-problem\">Q.1: What data structure is used in solving the Josephus problem?<\/a><\/li><li><a href=\"#q2-how-to-solve-the-josephus-problem\">Q.2: How to solve the Josephus problem?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>There are <strong>N<\/strong> people standing in a circle numbered from <strong>1<\/strong> to <strong>N<\/strong>. Also given an integer <strong>K<\/strong>. First, count the <strong>K-th<\/strong> number starting from the first one and delete it. Then <strong>K<\/strong> numbers are counted starting from the next one and the <strong>K-th<\/strong> one is removed again, and so on. The process stops when one number remains. The task is to find the last number.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"735\"  height=\"731\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"K Number\"  class=\"wp-image-3160 pk-lazyload\"  data-pk-sizes=\"auto\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/K-numbers.gif\" ><\/figure>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<ul><li><strong>Input: <\/strong>N = 6, K = 2<\/li><li><strong>Output: <\/strong>5<\/li><\/ul>\n\n\n\n<p><strong>Explanation<\/strong>:<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"809\"  height=\"773\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"output explanation\"  class=\"wp-image-3122 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 809px) 100vw, 809px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image1-3.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image1-3.png 809w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image1-3-300x287.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image1-3-768x734.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image1-3-380x363.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image1-3-550x526.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image1-3-800x764.png 800w\" ><\/figure>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"recursive-approach\">Recursive Approach<\/h2>\n\n\n\n<p>A simple approach to solve this problem is to find the position of the step which would be called after each execution.<\/p>\n\n\n\n<p>Therefore, given <strong>N<\/strong> persons, and skipping <strong>K<\/strong> persons during their deletion, <strong>N &#8211; 1<\/strong> persons will be left. Therefore, we need to call the recursive function for <strong>N &#8211; 1<\/strong> and <strong>K<\/strong> for the next iteration.<\/p>\n\n\n\n<p>Now, for each remaining circle after execution, we need to find the last remaining person present i.e. if <strong>Kth <\/strong>person is executed, <strong>K+1th<\/strong> will be the next starting safe point the recursive call. Therefore, to keep a track of the position, perform <strong>K%N + 1.<\/strong><\/p>\n\n\n\n<p>The recursive function would be:<\/p>\n\n\n\n<p><strong>josephus(N, K) = (josephus(N &#8211; 1 , K) + K &#8211; 1) % N + 1<\/strong>.<\/p>\n\n\n\n<p>You can also observe a pattern as follows:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"480\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Recursive Approach\"  class=\"wp-image-3123 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image2-2-1024x480.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image2-2-1024x480.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image2-2-300x141.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image2-2-768x360.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image2-2-1536x720.png 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image2-2-380x178.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image2-2-550x258.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image2-2-800x375.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image2-2-1160x544.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image2-2.png 1557w\" ><\/figure>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>If <strong>N&nbsp; == 1, <\/strong>return <strong>1<\/strong>. This is the termination condition for the function.<\/li><li>Else, return <strong>(josephus(N &#8211; 1 , K) + K &#8211; 1) % N + 1<\/strong>.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code\"><span id=\"c-code-2\">C++ Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int josephus(int N, int K) {\n  if (N == 1)\n    return 1;\n  else\n    return (josephus(N - 1, K) + K - 1) % N + 1;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\"><span id=\"java-code-2\">Java Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> static int josephus(int N, int K) {\n  if (N == 1)\n    return 1;\n  else\n    return (josephus(N - 1, K) + K - 1) % N + 1;\n}<\/pre>\n\n\n\n<h3 id=\"python-code\"><span id=\"python-code-2\">Python Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def josephus(N, K):\n \n    if N == 1:\n        return 1\n    else:\n        return (josephus(N - 1, K) + K - 1) % N + 1<\/pre>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(N)<\/li><li><strong>Space Complexity:<\/strong> O(N), depth of the recursion tree.<\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"using-list---approach-2\"><span id=\"using-list-approach-2\">Using List &#8211; Approach 2<\/span><\/h2>\n\n\n\n<p>In this approach, initialize a list containing all integers from <strong>1<\/strong> to <strong>N<\/strong> and delete every <strong>Kth<\/strong> node until one element is left.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"629\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"using list\"  class=\"wp-image-3161 pk-lazyload\"  data-pk-sizes=\"auto\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Using-List-Approach.gif\" ><\/figure>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>Create a list containing integers from <strong>1<\/strong> to <strong>N<\/strong>.<\/li><li>Create a recursive function which deletes every <strong>Kth element<\/strong> from the list in each iteration in the clockwise direction.<\/li><li>Continue repeating the above steps until only one element is left.<\/li><\/ul>\n\n\n\n<p><strong>Implementation of the Approach:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\"><span id=\"c-code-3\">C++ Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">void Josh(vector &lt; int > person, int k, int index) {\n  if (person.size() == 1) {\n    cout &lt;&lt; person[0] &lt;&lt; endl;\n    return;\n  }\n  index = ((index + k) % person.size());\n  person.erase(person.begin() + index);\n  Josh(person, k, index);\n}\n \nsolve(n, k) {\n  k--;\n  int index = 0;\n \n  vector &lt; int > person;\n  for (int i = 1; i &lt;= n; i++) {\n    person.push_back(i);\n  }\n \n  Josh(person, k, index);\n}<\/pre>\n\n\n\n<h3 id=\"java-code\"><span id=\"java-code-3\">Java Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> static void Josh(ArrayList &lt; Integer > person, int k, int index) {\n  if (person.size == 1) {\n    System.out.println(person.get(0));\n    return;\n  }\n  index = ((index + k) % person.size());\n  person.remove(index);\n  Josh(person, k, index);\n}\n \nsolve(int N, int K) {\n  K = K - 1;\n  int index = 0;\n \n  Arraylist &lt; Integer > person;\n  for (int i = 1; i &lt;= N; i++) {\n    person.push_back(i);\n  }\n \n  Josh(person, K, index);\n}<\/pre>\n\n\n\n<h3 id=\"python-code\"><span id=\"python-code-3\">Python Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def Josh(person, k, index):\n    if len(person) == 1:\n        print(person[0])\n        return\n \n    index = (index + k) % len(person)\n    person.pop(index)\n    Josh(person, k, index)\n \n \ndef solve(N, K):\n \n    K = K - 1\n    index = 0\n \n    persons = [0] * (N)\n    for i in range(1, N + 1):\n        person.append(i)\n \n    Josh(person, K, index)<\/pre>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(N), where N is total persons.<\/li><li><strong>Space Complexity:<\/strong> O(N), a list of size N<strong>, <\/strong>is used<strong>.<\/strong><\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"special-case-k--2\"><span id=\"special-case-k-2\">Special Case: K = 2<\/span><\/h2>\n\n\n\n<p>For K = 2, the problem becomes much easier to solve.<\/p>\n\n\n\n<p>In case, <strong>N <\/strong>is even, first all even positions will get deleted. Then, the remaining <strong>N \/ 2<\/strong> remains. Therefore, the answer for the remaining <strong>N <\/strong>can be found from the answer for <strong>N \/ 2 <\/strong>by multiplying it with <strong>2<\/strong> and subtracting <strong>1<\/strong> i.e. shifting the positions.<\/p>\n\n\n\n<p>The answer for even <strong>N<\/strong> can obtained as &#8211;<\/p>\n\n\n\n<p><strong>josephus(2 * N, 2) =&nbsp; josephus(N, 2) &#8211; 1<\/strong><\/p>\n\n\n\n<p>Similarly, In case, <strong>N <\/strong>is odd, first, all even positions will get deleted. Then, remaining (<strong>N &#8211; 1) \/ 2<\/strong> remains. Therefore, the answer for the remaining <strong>N <\/strong>can be found from the answer for (<strong>N &#8211; 1) \/ 2 <\/strong>by multiplying it with <strong>2<\/strong> and subtracting <strong>1<\/strong> i.e. shifting the positions.<\/p>\n\n\n\n<p>The answer for even <strong>N<\/strong> can obtained as &#8211;<\/p>\n\n\n\n<p><strong>josephus(2 * N + 1, 2) =&nbsp; josephus(N, 2) &#8211; 1<\/strong><\/p>\n\n\n\n<p>From the above relations, both can be merged and can be written as &#8211;<\/p>\n\n\n\n<p><strong>josephus(N, 2) = 1 + 2 * (N &#8211; 2 ^(floor(log2(N))<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int josephus(int N) {\n  int p = 1;\n  while (p &lt;= N)\n    p *= 2;\n \n  return (2 * N) - p + 1;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> static int josephus(int N) {\n  int p = 1;\n  while (p &lt;= N)\n    p *= 2;\n \n  return (2 * N) - p + 1;\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def josephus(N):\n    p = 1\n    while p &lt;= N:\n        p *= 2\n \n    return (2 * N) - p + 1<\/pre>\n\n\n\n<ul><li><strong>Time Complexity:<\/strong> O(logN), where N is the total steps.<\/li><li><strong>Space Complexity:<\/strong> O(1), as no extra s[ace<strong> <\/strong>is used<strong>.<\/strong><\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-question\">Practice Question<\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/100-people-in-a-circle\/\" target=\"_blank\">100 People In A Circle<\/a><\/li><\/ul>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<h3 id=\"q1-what-data-structure-is-used-in-solving-the-josephus-problem\"><span id=\"q-1-what-data-structure-is-used-in-solving-the-josephus-problem\">Q.1: What data structure is used in solving the Josephus problem?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>A list can be used to solve the Josephus problem, which initially contains all the integers from 1 to N.<\/p>\n\n\n\n<h3 id=\"q2-how-to-solve-the-josephus-problem\"><span id=\"q-2-how-to-solve-the-josephus-problem\">Q.2: How to solve the Josephus problem?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>The Josephus problem can be solved using recursion. For each iteration, recursively delete the Kth position until only one person is left.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement There are N people standing in a circle numbered from 1 to N. Also given an&hellip;\n","protected":false},"author":5,"featured_media":3158,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[483],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2888"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2888"}],"version-history":[{"count":13,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2888\/revisions"}],"predecessor-version":[{"id":22988,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2888\/revisions\/22988"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3158"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2888"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2888"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2888"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}