Question

2303. Calculate Amount Paid in Taxes

中文文档

Description

You are given a 0-indexed 2D integer array brackets where brackets[i] = [upperi, percenti] means that the ith tax bracket has an upper bound of upperi and is taxed at a rate of percenti. The brackets are sorted by upper bound (i.e. upperi-1 < upperi for 0 < i < brackets.length).

Tax is calculated as follows:

• The first upper0 dollars earned are taxed at a rate of percent0.
• The next upper1 - upper0 dollars earned are taxed at a rate of percent1.
• The next upper2 - upper1 dollars earned are taxed at a rate of percent2.
• And so on.

You are given an integer income representing the amount of money you earned. Return _the amount of money that you have to pay in taxes._ Answers within 10-5 of the actual answer will be accepted.

 

Example 1:

Input: brackets = [[3,50],[7,10],[12,25]], income = 10
Output: 2.65000
Explanation:
Based on your income, you have 3 dollars in the 1st tax bracket, 4 dollars in the 2nd tax bracket, and 3 dollars in the 3rd tax bracket.
The tax rate for the three tax brackets is 50%, 10%, and 25%, respectively.
In total, you pay $3 * 50% + $4 * 10% + $3 * 25% = $2.65 in taxes.

Example 2:

Input: brackets = [[1,0],[4,25],[5,50]], income = 2
Output: 0.25000
Explanation:
Based on your income, you have 1 dollar in the 1st tax bracket and 1 dollar in the 2nd tax bracket.
The tax rate for the two tax brackets is 0% and 25%, respectively.
In total, you pay $1 * 0% + $1 * 25% = $0.25 in taxes.

Example 3:

Input: brackets = [[2,50]], income = 0
Output: 0.00000
Explanation:
You have no income to tax, so you have to pay a total of $0 in taxes.

 

Constraints:

• 1 <= brackets.length <= 100
• 1 <= upperi <= 1000
• 0 <= percenti <= 100
• 0 <= income <= 1000
• upperi is sorted in ascending order.
• All the values of upperi are unique.
• The upper bound of the last tax bracket is greater than or equal to income.

Solutions

Solution 1: Simulation

We traverse brackets, and for each tax bracket, we calculate the tax amount for that bracket, then accumulate it.

The time complexity is $O(n)$, where $n$ is the length of brackets. The space complexity is $O(1)$.

class Solution:
  def calculateTax(self, brackets: List[List[int]], income: int) -> float:
    ans = prev = 0
    for upper, percent in brackets:
      ans += max(0, min(income, upper) - prev) * percent
      prev = upper
    return ans / 100

class Solution {
  public double calculateTax(int[][] brackets, int income) {
    int ans = 0, prev = 0;
    for (var e : brackets) {
      int upper = e[0], percent = e[1];
      ans += Math.max(0, Math.min(income, upper) - prev) * percent;
      prev = upper;
    }
    return ans / 100.0;
  }
}

class Solution {
public:
  double calculateTax(vector<vector<int>>& brackets, int income) {
    int ans = 0, prev = 0;
    for (auto& e : brackets) {
      int upper = e[0], percent = e[1];
      ans += max(0, min(income, upper) - prev) * percent;
      prev = upper;
    }
    return ans / 100.0;
  }
};

func calculateTax(brackets [][]int, income int) float64 {
  var ans, prev int
  for _, e := range brackets {
    upper, percent := e[0], e[1]
    ans += max(0, min(income, upper)-prev) * percent
    prev = upper
  }
  return float64(ans) / 100.0
}

function calculateTax(brackets: number[][], income: number): number {
  let ans = 0;
  let prev = 0;
  for (const [upper, percent] of brackets) {
    ans += Math.max(0, Math.min(income, upper) - prev) * percent;
    prev = upper;
  }
  return ans / 100;
}

impl Solution {
  pub fn calculate_tax(brackets: Vec<Vec<i32>>, income: i32) -> f64 {
    let mut res = 0f64;
    let mut pre = 0i32;
    for bracket in brackets.iter() {
      res += f64::from(income.min(bracket[0]) - pre) * f64::from(bracket[1]) * 0.01;
      if income <= bracket[0] {
        break;
      }
      pre = bracket[0];
    }
    res
  }
}