We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Calculate Amount Paid in Taxes

Number: 1382

Difficulty: Easy

Paid? No

Companies: Snowflake, Oracle, Meta

Problem Description

Given a sorted 2D array of tax brackets where each element represents an upper bound and its corresponding tax percentage, calculate the total tax payable on a given income. Each bracket taxes only the portion of income within its range, and the computation stops once the entire income has been processed.

Key Insights

  • Iterate through each tax bracket sequentially.
  • For each bracket, compute the amount of income that falls into that bracket (using the minimum of the bracket's upper bound and the total income).
  • Subtract the part of income already taxed from previous brackets.
  • Multiply the taxable amount in the current bracket by the tax rate (converted to a fraction).
  • Stop processing when the full income has been taxed.
  • Use simulation with constant space to efficiently solve the problem.

Space and Time Complexity

Time Complexity: O(n), where n is the number of tax brackets.
Space Complexity: O(1), using constant extra space.

Solution

The solution involves simulating the tax calculation across tax brackets. We iterate through each bracket and determine:

  1. The amount of income that should be taxed in the current bracket (by taking the difference between the bracket's upper bound and the previous bracket's upper bound, capped by the total income).
  2. The tax for that bracket, computed by applying the bracket's tax percentage on the calculated income segment.
  3. We update the cumulative income taxed and break out of the loop when the taxed amount meets or exceeds the total income. This simulation approach is straightforward and efficient given the problem constraints.

Code Solutions

def calculate_tax(brackets, income):
    # Initialize total tax to 0 and track previous upper bound (start at 0)
    tax = 0.0
    prev = 0
    # Iterate over each tax bracket, each represented as [upper, percent]
    for upper, percent in brackets:
        # Determine the taxable income in the current bracket
        amount = min(income, upper) - prev
        if amount > 0:
            tax += amount * (percent / 100)
            prev += amount
        # If the total taxed income reaches or exceeds the given income, exit loop
        if prev >= income:
            break
    return tax

# Example usage:
brackets = [[3, 50], [7, 10], [12, 25]]
income = 10
print(calculate_tax(brackets, income))
← Back to All Questions