Compute Progressive Income Tax in Cents from Bracket Limits

Income is taxed in brackets. Each bracket has an upper limit and a tax rate: the part of the income up to the first limit is taxed at the first rate, the part between the first and second limits at the second rate, and so on. Given the brackets and an income, return the tax owed.

Function Signature

def tax_in_cents(brackets: list[list[int]], income: int) -> int:

Rules

• brackets[i] = [upper, percent], and the brackets are sorted by strictly increasing upper.
• Bracket 0 covers income from 0 up to brackets[0][0]. For i >= 1, bracket i covers the income above brackets[i - 1][0] and up to brackets[i][0].
• The part of the income that falls in bracket i is taxed at brackets[i][1] percent.
• The income and the limits are whole dollars. Return the total tax in cents, that is the tax in dollars multiplied by 100, which is always a whole number under these inputs.

Constraints

• 1 <= len(brackets) <= 100
• 1 <= upper <= 10^6 for every bracket, strictly increasing
• 0 <= percent <= 100 for every bracket
• 0 <= income <= 10^6, and income is at most the last bracket's upper.

Examples

Example 1

Input: brackets = [[10000, 0], [40000, 10], [100000, 20]], income = 55000
Output: 600000

The first 10,000 dollars are untaxed, the next 30,000 are taxed at 10 percent (3,000 dollars), and the remaining 15,000 at 20 percent (3,000 dollars). The total is 6,000 dollars, or 600,000 cents.

Example 2

Input: brackets = [[1, 0], [4, 25], [5, 50]], income = 2
Output: 25

One dollar is taxed at 0 percent and one dollar at 25 percent, which is 25 cents. The last bracket is never reached.

Example 3

Input: brackets = [[2, 50]], income = 0
Output: 0