algoadvance

• You are given a 2D integer array brackets where brackets[i] = [upper_i, percent_i] represents the i^th tax bracket and a constant integer income representing your income.
• Each bracket is represented as a pair [upper, percent] where:
  • upper is the upper bound (inclusive) of the income while percent is the tax rate on the income within this bracket.
  • The lower bound of the i^th tax bracket is the upper bound of the (i-1)^th tax bracket plus 1.
• Each percent value is an integer representing a percentage, and income is an integer.
• Implement a function that calculates the total tax an individual has to pay based on the given tax brackets and income.

Clarifying Questions

1. Can brackets be empty?
   • No, brackets will always contain at least one bracket.
2. Is income guaranteed to be within the range covered by the brackets?
   • Yes, the problem guarantees that any income will be covered by the given brackets.
3. Are the brackets sorted by their upper bounds?
   • Yes, the brackets are sorted in non-decreasing order by their upper bounds.

Strategy

1. Initialize the total tax as 0.
2. Iterate through each bracket and calculate the income segment that falls within that bracket.
3. For each bracket, compute the taxable amount and multiply it by the bracket’s percentage to get the tax for that segment.
4. Accumulate the tax for all segments. Once the income falls within or below the upper bound of a bracket, break out of the loop as all the income has been taxed.

Code

def calculateTax(brackets, income):
    total_tax = 0
    previous_upper_bound = 0  # This keeps track of the lower bound of the current bracket
    
    for upper, percent in brackets:
        if income > upper:
            taxable_income = upper - previous_upper_bound
        else:
            taxable_income = income - previous_upper_bound
        
        total_tax += taxable_income * percent / 100
        
        # If the income is less than or equal to the upper bound, we've processed all taxable income
        if income <= upper:
            break
        
        # Update previous upper bound to the current upper for the next iteration
        previous_upper_bound = upper
    
    return total_tax

# Example usage
brackets = [[3000, 10], [5000, 20], [10000, 30]]
income = 4500
print(calculateTax(brackets, income))  # Expected result is the calculated tax amount

Time Complexity

• The time complexity of this solution is (O(n)), where (n) is the number of tax brackets.
• The space complexity is (O(1)) since we are only using a few extra variables to store intermediate results.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?