Compute Progressive Income Tax in Cents from Bracket Limits
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
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**
```text
Input: brackets = [[2, 50]], income = 0
Output: 0
```
Overview: Given progressive tax brackets as upper limits with percentage rates and an income in whole dollars, return the total tax owed in cents. It tests careful handling of bracket boundaries, partly filled brackets and exact integer arithmetic instead of floating point.
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 total tax owed, in cents.
You are given `brackets`, where `brackets[i] = [upper, percent]` and the brackets are sorted by strictly increasing `upper`, and an integer `income`.
- 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. A bracket that lies entirely above the income receives no income and adds no tax.
- 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.
- The answer is at most 10^6 * 100 = 10^8 cents, so it never exceeds 2^31 - 1 and fits in a 32-bit signed integer.
**Example 1**
```text
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**
```text
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.
**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`.
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
Input: ([[10000, 0], [40000, 10], [100000, 20]], 55000)
Expected Output: 600000
Explanation: Source Example 1: 10000*0 + 30000*10 + 15000*20 = 600000 cents; a flat rate on the whole income would give 1100000.
Input: ([[1, 0], [4, 25], [5, 50]], 2)
Expected Output: 25
Explanation: Source Example 2: 1*0 + 1*25 = 25 cents; the last bracket is never reached, and whole-dollar truncation would wrongly give 0.
Hints
- What is p percent of d whole dollars when expressed in cents? See whether you can avoid fractions entirely.
- For each bracket, how many dollars of the income lie above the previous limit and at or below this bracket's limit? What should that amount be when the income does not reach the bracket?
- Check an income that lands exactly on a bracket limit: which bracket does that last dollar belong to?