{x}
blog image

Calculate Amount Paid in Taxes

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.

2303. Calculate Amount Paid in Taxes

Problem Description

You are given a 0-indexed 2D integer array brackets where brackets[i] = [upper<sub>i</sub>, percent<sub>i</sub>] means that the ith tax bracket has an upper bound of upper<sub>i</sub> and is taxed at a rate of percent<sub>i</sub>. The brackets are sorted by upper bound. You are also given an integer income representing your earnings. The task is to calculate the total tax amount you need to pay.

Solution Explanation

The solution uses a simple iterative approach to calculate the tax. We iterate through each tax bracket. For each bracket, we determine the taxable income within that bracket and calculate the tax for that portion using the corresponding tax rate. The total tax is the sum of taxes from all applicable brackets.

Algorithm:

  1. Initialization: Initialize total_tax to 0 and previous_upper_bound to 0.
  2. Iteration: Iterate through the brackets array.
  3. Taxable Income: For each bracket [upper, percent], calculate the taxable income within that bracket:
    • taxable_income = min(income, upper) - previous_upper_bound
    • taxable_income is capped at 0 to avoid negative values if income is less than the current bracket's lower bound.
  4. Tax Calculation: Calculate the tax for the current bracket:
    • bracket_tax = taxable_income * (percent / 100.0)
  5. Accumulation: Add bracket_tax to total_tax.
  6. Update: Update previous_upper_bound to upper.
  7. Return: After iterating through all brackets, return total_tax.

Time and Space Complexity

Time Complexity: O(n), where n is the number of tax brackets. We iterate through the brackets array once.

Space Complexity: O(1). We use a constant amount of extra space to store variables like total_tax and previous_upper_bound.

Code Implementation

Python:

def calculateTax(brackets, income):
    total_tax = 0
    previous_upper_bound = 0
    for upper, percent in brackets:
        taxable_income = max(0, min(income, upper) - previous_upper_bound)
        total_tax += taxable_income * (percent / 100.0)
        previous_upper_bound = upper
    return total_tax

Java:

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

C++:

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

Go:

func calculateTax(brackets [][]int, income int) float64 {
    totalTax := 0.0
    prevUpper := 0
    for _, bracket := range brackets {
        upper := bracket[0]
        percent := bracket[1]
        taxableIncome := max(0, min(income, upper) - prevUpper)
        totalTax += float64(taxableIncome) * float64(percent) / 100.0
        prevUpper = upper
    }
    return totalTax
}
 
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
 
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

JavaScript:

const calculateTax = (brackets, income) => {
    let totalTax = 0;
    let prevUpper = 0;
    for (const [upper, percent] of brackets) {
        const taxableIncome = Math.max(0, Math.min(income, upper) - prevUpper);
        totalTax += taxableIncome * (percent / 100);
        prevUpper = upper;
    }
    return totalTax;
};

These code implementations all follow the same algorithm and achieve the same result, differing only in syntax and specific language features. They all have the same time and space complexity as described above.