Calculate Amount Paid in Taxes
In this problem, we need to calculate the total tax amount from the given income and tax brackets. We traverse through each tax bracket from the lowest to highest. In each bracket, we calculate the taxable income as the minimum of the income and the upper limit of the bracket. The tax for this bracket is then calculated by multiplying the taxable income with the tax rate. This process continues until we exhaust the income or all brackets.
Python solution:


We maintain a variable previous_upper
to keep track of the upper limit of the previous tax bracket. This is needed to calculate the taxable income for the current tax bracket.
The complexity of the solution is O(n) where n is the number of tax brackets, as we potentially need to traverse all the brackets.