{"id":9748,"date":"2022-06-14T19:41:32","date_gmt":"2022-06-15T02:41:32","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9748"},"modified":"2022-06-14T20:53:19","modified_gmt":"2022-06-15T03:53:19","slug":"leetcode-2303-calculate-amount-paid-in-taxes","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-2303-calculate-amount-paid-in-taxes\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2303. Calculate Amount Paid in Taxes"},"content":{"rendered":"\n<p>You are given a&nbsp;<strong>0-indexed<\/strong>&nbsp;2D integer array&nbsp;<code>brackets<\/code>&nbsp;where&nbsp;<code>brackets[i] = [upper<sub>i<\/sub>, percent<sub>i<\/sub>]<\/code>&nbsp;means that the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;tax bracket has an upper bound of&nbsp;<code>upper<sub>i<\/sub><\/code>&nbsp;and is taxed at a rate of&nbsp;<code>percent<sub>i<\/sub><\/code>. The brackets are&nbsp;<strong>sorted<\/strong>&nbsp;by upper bound (i.e.&nbsp;<code>upper<sub>i-1<\/sub>&nbsp;&lt; upper<sub>i<\/sub><\/code>&nbsp;for&nbsp;<code>0 &lt; i &lt; brackets.length<\/code>).<\/p>\n\n\n\n<p>Tax is calculated as follows:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>The first&nbsp;<code>upper<sub>0<\/sub><\/code>&nbsp;dollars earned are taxed at a rate of&nbsp;<code>percent<sub>0<\/sub><\/code>.<\/li><li>The next&nbsp;<code>upper<sub>1<\/sub>&nbsp;- upper<sub>0<\/sub><\/code>&nbsp;dollars earned are taxed at a rate of&nbsp;<code>percent<sub>1<\/sub><\/code>.<\/li><li>The next&nbsp;<code>upper<sub>2<\/sub>&nbsp;- upper<sub>1<\/sub><\/code>&nbsp;dollars earned are taxed at a rate of&nbsp;<code>percent<sub>2<\/sub><\/code>.<\/li><li>And so on.<\/li><\/ul>\n\n\n\n<p>You are given an integer&nbsp;<code>income<\/code>&nbsp;representing the amount of money you earned. Return&nbsp;<em>the amount of money that you have to pay in taxes.<\/em>&nbsp;Answers within&nbsp;<code>10<sup>-5<\/sup><\/code>&nbsp;of the actual answer will be accepted.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> brackets = [[3,50],[7,10],[12,25]], income = 10\n<strong>Output:<\/strong> 2.65000\n<strong>Explanation:<\/strong>\nThe first 3 dollars you earn are taxed at 50%. You have to pay $3 * 50% = $1.50 dollars in taxes.\nThe next 7 - 3 = 4 dollars you earn are taxed at 10%. You have to pay $4 * 10% = $0.40 dollars in taxes.\nThe final 10 - 7 = 3 dollars you earn are taxed at 25%. You have to pay $3 * 25% = $0.75 dollars in taxes.\nYou have to pay a total of $1.50 + $0.40 + $0.75 = $2.65 dollars in taxes.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> brackets = [[1,0],[4,25],[5,50]], income = 2\n<strong>Output:<\/strong> 0.25000\n<strong>Explanation:<\/strong>\nThe first dollar you earn is taxed at 0%. You have to pay $1 * 0% = $0 dollars in taxes.\nThe second dollar you earn is taxed at 25%. You have to pay $1 * 25% = $0.25 dollars in taxes.\nYou have to pay a total of $0 + $0.25 = $0.25 dollars in taxes.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> brackets = [[2,50]], income = 0\n<strong>Output:<\/strong> 0.00000\n<strong>Explanation:<\/strong>\nYou have no income to tax, so you have to pay a total of $0 dollars in taxes.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= brackets.length &lt;= 100<\/code><\/li><li><code>1 &lt;= upper<sub>i<\/sub>&nbsp;&lt;= 1000<\/code><\/li><li><code>0 &lt;= percent<sub>i<\/sub>&nbsp;&lt;= 100<\/code><\/li><li><code>0 &lt;= income &lt;= 1000<\/code><\/li><li><code>upper<sub>i<\/sub><\/code>&nbsp;is sorted in ascending order.<\/li><li>All the values of&nbsp;<code>upper<sub>i<\/sub><\/code>&nbsp;are&nbsp;<strong>unique<\/strong>.<\/li><li>The upper bound of the last tax bracket is greater than or equal to&nbsp;<code>income<\/code>.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Follow the rules<\/strong><\/h2>\n\n\n\n<p>&#8220;Nothing is certain except death and taxes&#8221; &#8211; Benjamin Franklin<\/p>\n\n\n\n<p>Time complexity: O(n)<br>Space complexity: O(1)<\/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\nclass Solution {\npublic:\n  double calculateTax(vector<vector<int>>& A, int income) {\n    double ans = 0;\n    for (int i = 0; i < A.size(); ++i) {      \n      ans += (min(income, A[i][0]) - (i ? A[i-1][0] : 0)) * A[i][1] \/ 100.0;      \n      if (A[i][0] >= income) break;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given a&nbsp;0-indexed&nbsp;2D integer array&nbsp;brackets&nbsp;where&nbsp;brackets[i] = [upperi, percenti]&nbsp;means that the&nbsp;ith&nbsp;tax bracket has an upper bound of&nbsp;upperi&nbsp;and is taxed at a rate of&nbsp;percenti. The brackets&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[222],"class_list":["post-9748","post","type-post","status-publish","format-standard","hentry","category-array","tag-easy","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9748","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=9748"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9748\/revisions"}],"predecessor-version":[{"id":9750,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9748\/revisions\/9750"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9748"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9748"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9748"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}