{"id":4811,"date":"2019-02-09T12:44:02","date_gmt":"2019-02-09T20:44:02","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4811"},"modified":"2019-02-09T12:49:25","modified_gmt":"2019-02-09T20:49:25","slug":"leetcode-781-rabbits-in-forest","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-781-rabbits-in-forest\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 781. Rabbits in Forest"},"content":{"rendered":"\n<p>In a forest, each rabbit has some color. Some subset of rabbits (possibly all of them) tell you how many other rabbits have the same color as them. Those&nbsp;<code>answers<\/code>&nbsp;are placed in an array.<\/p>\n\n\n\n<p>Return the minimum number of rabbits that could be in the forest.<\/p>\n\n\n\n<pre class=\"wp-block-preformatted crayon:false\"><strong>Examples:<\/strong>\n<strong>Input:<\/strong> answers = [1, 1, 2]\n<strong>Output:<\/strong> 5\n<strong>Explanation:<\/strong>\nThe two rabbits that answered \"1\" could both be the same color, say red.\nThe rabbit than answered \"2\" can't be red or the answers would be inconsistent.\nSay the rabbit that answered \"2\" was blue.\nThen there should be 2 other blue rabbits in the forest that didn't answer into the array.\nThe smallest possible number of rabbits in the forest is therefore 5: 3 that answered plus 2 that didn't.\n\n<strong>Input:<\/strong> answers = [10, 10, 10]\n<strong>Output:<\/strong> 11\n\n<strong>Input:<\/strong> answers = []\n<strong>Output:<\/strong> 0\n<\/pre>\n\n\n\n<p><strong>Note:<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\"><li><code>answers<\/code>&nbsp;will have length at most&nbsp;<code>1000<\/code>.<\/li><li>Each&nbsp;<code>answers[i]<\/code>&nbsp;will be an integer in the range&nbsp;<code>[0, 999]<\/code>.<\/li><\/ol>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Math<\/strong><\/h2>\n\n\n\n<p>Say there n rabbits answered x. <br>if n &lt;= x: they can have the same color<br>if n &gt; x: they must be divided into groups, each group has x + 1 rabbits, and there are at least ceil(n \/ (x+1)) groups. <br> So there will be ceil(n \/ (x + 1)) * (x + 1) rabbits. This expression can be expressed as (n + x) \/ (x + 1) * (x + 1) in programming languages. (n + x) \/\/ (x + 1) * (x + 1) for Python3.<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua, running time: 8 ms \/ 5.2 MB\nclass Solution {\npublic:\n  int numRabbits(vector<int>& answers) {\n    vector<int> counts(*max_element(begin(answers), end(answers)) + 1);\n    for (const int answer : answers)\n      ++counts[answer];\n    int total = 0;\n    for (int x = 0; x < counts.size(); ++x)\n      total += (counts[x] + x) \/ (x + 1) * (x + 1);\n    return total;\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua, running time: 36 ms \/ 6.5 MB\nclass Solution:\n  def numRabbits(self, answers: 'List[int]') -> 'int':\n    counts = collections.Counter(answers)\n    return sum([(n + x) \/\/ (x + 1) * (x + 1) for x, n in counts.items()])\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>In a forest, each rabbit has some color. Some subset of rabbits (possibly all of them) tell you how many other rabbits have the same&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[31,177],"class_list":["post-4811","post","type-post","status-publish","format-standard","hentry","category-math","tag-math","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4811","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4811"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4811\/revisions"}],"predecessor-version":[{"id":4815,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4811\/revisions\/4815"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4811"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4811"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4811"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}