{"id":4869,"date":"2021-12-13T17:13:02","date_gmt":"2021-12-13T11:43:02","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=4869"},"modified":"2022-06-15T11:49:35","modified_gmt":"2022-06-15T06:19:35","slug":"friends-pairing-problem","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/friends-pairing-problem\/","title":{"rendered":"Friends Pairing Problem (Solution)"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">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-brute-force-method\">Recursive Brute Force Method<\/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=\"#approach-2-memoization\">Approach 2: Memoization<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#approach-3-iterative-dynamic-programming\">Approach 3: Iterative Dynamic Programming<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#approach-4-combinatorics-based-approach\">Approach 4: Combinatorics Based 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=\"#faqs\">FAQs<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a total of n friends, each friend can either remain single or can be paired up with some other friend. The pairing for each friend can be done only once. Find out the total number of ways in which the friends can be single or get paired up.<\/p>\n\n\n\n<p><strong>Sample Test Cases<\/strong><\/p>\n\n\n\n<p><strong>Input 1:<\/strong> n = 2<br><strong>Output 1:<\/strong> 2<br><strong>Explanation 1:<\/strong> There are only 2 ways for the pairings to be made, both friends get paired into 1 group or both friends remain single.<\/p>\n\n\n\n<p><strong>Input 2:<\/strong> n = 3<br><strong>Output 2:<\/strong> 4<br><strong>Explanation 2:<\/strong> The pairings are listed below:<br>{1}, {2}, {3}<br>{1, 2}, {3}<br>{1, 3}, {2}<br>{2, 3}, {1}<\/p>\n\n\n\n<h2 id=\"recursive-brute-force-method\">Recursive Brute Force Method<\/h2>\n\n\n\n<p>The problem can be solved with recursion by considering the choices we have for the <strong>nth<\/strong> person. For the nth person,<\/p>\n\n\n\n<ul><li>The <strong>nth<\/strong> person stays single or unpaired, and we recurse for the remaining <strong>n &#8211; 1<\/strong> people.<\/li><li><strong>Nth<\/strong> person pairs up with any for the remaining <strong>n &#8211; 1<\/strong> people. The number of ways of doing this <strong>(n &#8211; 1) * Rec(n &#8211; 2).<\/strong><\/li><\/ul>\n\n\n\n<p>The recurrence can then be written as:<\/p>\n\n\n\n<ul><li>Rec(n) = Rec(n &#8211; 1) + (n &#8211; 1) * Rec(n &#8211; 2)<\/li><\/ul>\n\n\n\n<p>Which can be easily simulated with brute force.<\/p>\n\n\n\n<p><strong>Base Case:<\/strong> Note that if there are 2 friends, there are 2 ways to arrange them, and for a single friend, there is only 1 way to arrange them. So for n &lt;= 2, the answer will be n.<\/p>\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 countPairings(int n) {\n    return n &lt;= 2 ? n : countPairings(n - 1) + (n - 1) * countPairings(n - 2);\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=\"\">public static int countPairings(int n) {\n        return n &lt;= 2 ? n : countPairings(n - 1) + (n - 1) * countPairings(n - 2);\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 countPairings(n):\n    return n if n &lt;= 2 else countPairings(n - 1) + (n - 1) *\ncountPairings(n - 2)<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> Exponential<br><strong>Space Complexity:<\/strong> O(1) \/\/ If recursion stack space is ignored.<\/p>\n\n\n\n<h2 id=\"approach-2-memoization\">Approach 2: Memoization<\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"569\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-5047 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\/12\/Recursion-Tree-1024x569.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Recursion-Tree-1024x569.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Recursion-Tree-300x167.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Recursion-Tree-768x427.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Recursion-Tree-380x211.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Recursion-Tree-550x306.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Recursion-Tree-800x445.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Recursion-Tree-1160x645.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Recursion-Tree.png 1447w\" ><\/figure>\n\n\n\n<p>Observe from the above recursion tree, that there are many subproblems in the brute force method which are being called again and again. We can <strong>memoize<\/strong> these subproblems so as to avoid them from being recalculated again and again with a dynamic programming approach.<\/p>\n\n\n\n<p>Here, the states of our dp will be <strong>dp[n]: Number of ways to arrange a total of n friends<\/strong>. The transitions will be the same as in the brute force approach.<\/p>\n\n\n\n<h3 id=\"c-implementation\"><span id=\"c-implementation-2\">C++ Implementation<\/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 countPairings(int n, vector &lt; int > &amp; dp) {\n  if (dp[n] != -1) {\n    return dp[n];\n  }\n  dp[n] = n &lt;= 2 ? n : countPairings(n - 1, dp) + (n - 1) * countPairings(n - 2, dp);\n  return dp[n];\n}<\/pre>\n\n\n\n<h3 id=\"java-implementation\"><span id=\"java-implementation-2\">Java Implementation<\/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=\"\">public static int countPairings(int n, int[] dp) {\n  if (dp[n] != -1) {\n    return dp[n];\n  }\n  dp[n] = n &lt;= 2 ? n : countPairings(n - 1, dp) + (n - 1) * countPairings(n - 2, dp);\n  return dp[n];\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation\"><span id=\"python-implementation-2\">Python Implementation<\/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 countPairings(n, dp):\n    if dp[n] != -1:\n        return dp[n]\n    dp[n] = n if n &lt;= 2 else countPairings(n - 1, dp) + (n - 1) * countPairings(n - 2, dp)\n    return dp[n]<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(n)<br><strong>Space Complexity:<\/strong> O(n)<\/p>\n\n\n\n<h2 id=\"approach-3-iterative-dynamic-programming\">Approach 3: Iterative Dynamic Programming<\/h2>\n\n\n\n<p>Similar to the recursive memoization-based <a href=\"https:\/\/www.interviewbit.com\/courses\/programming\/dynamic-programming\/\" target=\"_blank\" rel=\"noreferrer noopener\"><strong>dynamic programming<\/strong><\/a> approach, we can also solve the problem with an <strong>iterative dynamic programming-based approach<\/strong>, i.e with tabulation. The states and the transitions for this approach will be the same as the ones for the recursive approach just implemented in an iterative manner.<\/p>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/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 countPairings(int n) {\n  vector &lt; int > dp(n + 1);\n  for (int i = 0; i &lt;= n; i++) {\n    if (i &lt;= 2) {\n      dp[i] = i;\n    } else {\n      dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];\n    }\n  }\n  return dp[n];\n}<\/pre>\n\n\n\n<h3 id=\"java-implementation\">Java Implementation<\/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=\"\">public static int countPairings(int n) {\n  int dp[] = new int[n + 1];\n  for (int i = 0; i &lt;= n; i++) {\n    if (i &lt;= 2) {\n      dp[i] = i;\n    } else {\n      dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];\n    }\n  }\n  return dp[n];\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation\">Python Implementation<\/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 countPairings(n):\n    dp = [0] * (n + 1)\n    for i in range(n + 1):\n        if i &lt;= 2:\n            dp[i] = i\n        else:\n            dp[i] = dp[i - 1] + (i - 1) * dp[i - 2]\n    return dp[n]<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(n)<br><strong>Space Complexity:<\/strong> O(n)<\/p>\n\n\n\n<h2 id=\"approach-4-combinatorics-based-approach\">Approach 4: Combinatorics Based Approach<\/h2>\n\n\n\n<p>The problem given is basically equivalent to the combinatorial problem of <strong>\u201cIn how many ways can we divide a total of n items into multiple groups (maximum group size here being 2).\u201d <\/strong>This problem is solved by the following formula:<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"384\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-5048 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\/12\/Formula-1024x384.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Formula-1024x384.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Formula-300x113.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Formula-768x288.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Formula-380x143.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Formula-550x206.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Formula-800x300.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Formula-1160x435.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/Formula.png 1447w\" ><\/figure>\n\n\n\n<p>Referring to the above formula, we can precompute the factorials in our problem, and using them calculate the result from the given formula.<\/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 countPairings(int n) {\n  vector &lt; int > fact(n + 1);\n  fact[0] = 1;\n  for (int i = 1; i &lt;= n; i++) {\n    fact[i] = fact[i - 1] * i;\n  }\n  int groupsOfOnes = n, groupsOfTwos = 1, ans = 0;\n  while (groupsOfOnes >= 0) {\n    ans += fact[n] \/ (groupsOfTwos * fact[groupsOfOnes] * fact[(n - groupsOfOnes) \/ 2]);\n    groupsOfOnes -= 2;\n    groupsOfTwos &lt;&lt;= 1;\n  }\n  return ans;\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=\"\">public static int countPairings(int n) {\n  int fact[] = new int[n + 1];\n  fact[0] = 1;\n  for (int i = 1; i &lt;= n; i++) {\n    fact[i] = fact[i - 1] * i;\n  }\n  int groupsOfOnes = n, groupsOfTwos = 1, ans = 0;\n  while (groupsOfOnes >= 0) {\n    ans += fact[n] \/ (groupsOfTwos * fact[groupsOfOnes] * fact[(n - groupsOfOnes) \/ 2]);\n    groupsOfOnes -= 2;\n    groupsOfTwos &lt;&lt;= 1;\n  }\n  return ans;\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 countPairings(n):\n    fac = [1] * (n + 1)\n    for i in range(1, n + 1):\n        fac[i] = fac[i - 1] * i\n    groupsOfOnes = n\n    groupsOfTwos = 1\n    ans = 0\n    while groupsOfOnes >= 0:\n        ans += fac[n] \/\/ (\n            fac[groupsOfOnes] * fac[(n - groupsOfOnes) \/\/ 2] * groupsOfTwos\n        )\n        groupsOfOnes -= 2\n        groupsOfTwos &lt;&lt;= 1\n    return ans<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(n)<br><strong>Space Complexity:<\/strong> O(n)<\/p>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<p><strong>Q. How does the brute force approach have exponential time complexity?<\/strong><br>A. From the recursion tree, we can observe that the tree divides into two branches at each level. So the number of states to be visited becomes exponential in number when measured as a function of input n.<\/p>\n\n\n\n<p><strong>Q. How many states does the recursion depend upon in this problem?<\/strong><br>A. The recursion is solely dependent on the number of people (n) as the state for this problem.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a total of n friends, each friend can either remain single or can be paired&hellip;\n","protected":false},"author":5,"featured_media":5046,"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":[682],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4869"}],"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=4869"}],"version-history":[{"count":5,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4869\/revisions"}],"predecessor-version":[{"id":9812,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4869\/revisions\/9812"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/5046"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=4869"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=4869"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=4869"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}