{"id":4959,"date":"2019-03-09T22:01:54","date_gmt":"2019-03-10T06:01:54","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4959"},"modified":"2019-03-10T00:48:50","modified_gmt":"2019-03-10T08:48:50","slug":"leetcode-1006-clumsy-factorial","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/simulation\/leetcode-1006-clumsy-factorial\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1006. Clumsy Factorial"},"content":{"rendered":"\n

Normally, the factorial of a positive integer n<\/code> is the product of all positive integers less than or equal to n<\/code>.  For example, factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1<\/code>.<\/p>\n\n\n\n

We instead make a clumsy factorial:<\/em> using the integers in decreasing order, we swap out the multiply operations for a fixed rotation of operations: multiply (*), divide (\/), add (+) and subtract (-) in this order.<\/p>\n\n\n\n

For example, clumsy(10) = 10 * 9 \/ 8 + 7 - 6 * 5 \/ 4 + 3 - 2 * 1<\/code>.  However, these operations are still applied using the usual order of operations of arithmetic: we do all multiplication and division steps before any addition or subtraction steps, and multiplication and division steps are processed left to right.<\/p>\n\n\n\n

Additionally, the division that we use is floor division<\/em> such that 10 * 9 \/ 8<\/code> equals 11<\/code>.  This guarantees the result is an integer.<\/p>\n\n\n\n

Implement the clumsy<\/code> function as defined above: given an integer N<\/code>, it returns the clumsy factorial of N<\/code>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input: <\/strong>4\nOutput:<\/strong> 7\nExplanation:<\/strong> 7 = 4 * 3 \/ 2 + 1\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input: <\/strong>10\nOutput: <\/strong>12\nExplanation: <\/strong>12 = 10 * 9 \/ 8 + 7 - 6 * 5 \/ 4 + 3 - 2 * 1\n<\/pre>\n\n\n\n
Note:<\/strong><\/p>\n\n\n\n
  1. 1 <= N <= 10000<\/code><\/li>
  2. -2^31 <= answer <= 2^31 - 1<\/code>  (The answer is guaranteed to fit within a 32-bit integer.)<\/li><\/ol>\n\n\n\n
    Solution: Simulation<\/strong><\/h2>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua 4ms 8.2 MB\nclass Solution {\npublic:\n  int clumsy(int N) {\n    if (N <= 0) return 0;\n    if (N == 1) return 1;\n    if (N == 2) return 2 * 1;\n    if (N == 3) return 3 * 2 \/ 1;\n    \n    int ans = N * (N - 1) \/ (N - 2) + (N - 3);\n    \n    while ((N -= 4) >= 4)\n      ans = ans - N * (N - 1) \/ (N - 2) + (N - 3);\n    \n    return ans - clumsy(N);\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Normally, the factorial of a positive integer n is the product of all positive integers less than or equal to n.  For example, factorial(10) = 10 * 9 *…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48],"tags":[31,177,179],"class_list":["post-4959","post","type-post","status-publish","format-standard","hentry","category-simulation","tag-math","tag-medium","tag-simulation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4959","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=4959"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4959\/revisions"}],"predecessor-version":[{"id":4970,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4959\/revisions\/4970"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4959"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4959"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4959"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}