{"id":21128,"date":"2021-07-23T17:01:00","date_gmt":"2021-07-23T17:01:00","guid":{"rendered":"https:\/\/www.askpython.com\/?p=21128"},"modified":"2021-08-04T17:08:11","modified_gmt":"2021-08-04T17:08:11","slug":"friends-travel-problem","status":"publish","type":"post","link":"https:\/\/www.askpython.com\/python\/examples\/friends-travel-problem","title":{"rendered":"Solving the Friends-Travel Problem in Python [Google Interview Question]"},"content":{"rendered":"\n<p>In this tutorial, we will be understanding a very interesting problem known as\u00a0<strong>The Friends-Travel Problem<\/strong>. Let us first understand what do we want to achieve in this problem.<\/p>\n\n\n\n<hr class=\"wp-block-separator\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Friends-Travel Problem Explaination<\/h2>\n\n\n\n<p>Let us suppose n friends want to go to a party, they can travel either individually or along with a friend as a couple. We assume that for n friends, n motorbikes are available.<\/p>\n\n\n\n<p>We need to compute the number of ways the n friends can travel to the party, either individually or in pair of two as a couple.<\/p>\n\n\n\n<hr class=\"wp-block-separator\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Solution to the Friends-Travel Problem<\/h2>\n\n\n\n<p>One can either manually code the naive approach using loops and if-else conditions or can go for the faster approach which is the&nbsp;<strong>Recursion<\/strong>&nbsp;approach. If you want to know more about recursion read the tutorial mentioned below.<\/p>\n\n\n\n<p><strong><em>Read more about Recursion:&nbsp;<a href=\"https:\/\/www.askpython.com\/python\/python-recursion-function\" target=\"_blank\" rel=\"noreferrer noopener\">Recursion in Python<\/a><\/em><\/strong><\/p>\n\n\n\n<p>In order to solve a bigger problem, one needs to break a bigger problem into smaller problems. But before that, let&#8217;s look at the lower values of <strong>n<\/strong> ( 1, 2, and 3). <\/p>\n\n\n\n<p>For n = 1 and n = 2, there are only one and two possible ways respectively. And for n = 3, we have four possible cases. How?<\/p>\n\n\n\n<p>For every value of n, a friend has two choices, either the friend can travel alone and we can check for n-1 friends. <\/p>\n\n\n\n<p>Or the friend can choose a friend from the n-1 friends to travel with and then we check for n-2 friends.<\/p>\n\n\n\n<div class=\"wp-block-image is-style-default\"><figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"500\" height=\"500\" src=\"https:\/\/www.askpython.com\/wp-content\/uploads\/2021\/07\/Recursive_solution_Friends_Bike_Problem.png\" alt=\"Recursive Solution Friends Bike Problem\" class=\"wp-image-21132\" srcset=\"https:\/\/www.askpython.com\/wp-content\/uploads\/2021\/07\/Recursive_solution_Friends_Bike_Problem.png 500w, https:\/\/www.askpython.com\/wp-content\/uploads\/2021\/07\/Recursive_solution_Friends_Bike_Problem-300x300.png 300w, https:\/\/www.askpython.com\/wp-content\/uploads\/2021\/07\/Recursive_solution_Friends_Bike_Problem-150x150.png 150w\" sizes=\"auto, (max-width: 500px) 100vw, 500px\" \/><figcaption>Recursive Solution Friends Bike Problem<\/figcaption><\/figure><\/div>\n\n\n\n<hr class=\"wp-block-separator\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Code Implementation of the Friends-Bike Problem<\/h2>\n\n\n\n<p>The code implementation is very simple through recursion. Just make sure you have understood the solution explained earlier.<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; gutter: true; title: ; notranslate\" title=\"\">\ndef count_no_ways(n):\n    if(n&lt;3):\n        return n\n    return (count_no_ways(n-1)) + ((n-1) * count_no_ways(n-2))\n\nn = int(input(&quot;Enter the number of friends: &quot;))\nprint(count_no_ways(n))\n<\/pre><\/div>\n\n\n<hr class=\"wp-block-separator\"\/>\n\n\n\n<p>I hope the problem, solution, and code implementation are clear to you. Thank you for reading the tutorial!<\/p>\n\n\n\n<p>Happy learning! &#x1f607;<\/p>\n\n\n\n<hr class=\"wp-block-separator\"\/>\n","protected":false},"excerpt":{"rendered":"<p>In this tutorial, we will be understanding a very interesting problem known as\u00a0The Friends-Travel Problem. Let us first understand what do we want to achieve in this problem. Friends-Travel Problem Explaination Let us suppose n friends want to go to a party, they can travel either individually or along with a friend as a couple. [&hellip;]<\/p>\n","protected":false},"author":28,"featured_media":21489,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[],"class_list":["post-21128","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-examples"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts\/21128","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/users\/28"}],"replies":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/comments?post=21128"}],"version-history":[{"count":0,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/posts\/21128\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/media\/21489"}],"wp:attachment":[{"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/media?parent=21128"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/categories?post=21128"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.askpython.com\/wp-json\/wp\/v2\/tags?post=21128"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}