Calculate Tax from Progressive Brackets

Problem

Implement calculateProgressiveTax(income, upperBounds, ratesBps) -> tax.

income is a nonnegative integer number of minor currency units. ratesBps contains one marginal rate per tax bracket in basis points, where 10,000 basis points means 100%. upperBounds contains the exclusive upper income boundary of every bracket except the final open-ended bracket.

If ratesBps.length == m, then upperBounds.length == m - 1 and the brackets are:

• bracket 0: [0, upperBounds[0]) when m > 1;
• bracket i: [upperBounds[i - 1], upperBounds[i]) for each interior bracket;
• bracket m - 1: [upperBounds[m - 2], infinity) when m > 1;
• when m == 1, the single rate applies to all income.

Only the income slice inside a bracket is taxed at that bracket's rate. Compute the full tax numerator as the sum of slice * rateBps across brackets, then return floor(totalNumerator / 10,000). Round down once after summing all brackets; do not round each bracket separately.

Function Contract

• income is a JSON integer.
• upperBounds and ratesBps are JSON arrays of integers.
• Return one JSON integer tax in minor currency units.
• Do not mutate either input array.

Constraints

• 0 <= income <= 100,000,000,000.
• 1 <= ratesBps.length <= 200,000.
• upperBounds.length + 1 == ratesBps.length.
• Every boundary is in [1, 100,000,000,000], and boundaries are strictly increasing.
• Every rate is in [0, 10,000] basis points.
• The largest possible numerator is 1,000,000,000,000,000, which is exact in signed 64-bit arithmetic and in JavaScript's safe-integer range.
• Target O(m) time and O(1) auxiliary space, where m is the number of rates.

Examples

income = 50000
upperBounds = [10000, 40000]
ratesBps = [1000, 2000, 3000]
tax = 10000

The three taxable slices are 10000, 30000, and 10000 at 10%, 20%, and 30% respectively.

income = 40000
upperBounds = [10000, 40000]
ratesBps = [1000, 2000, 3000]
tax = 7000

An exclusive boundary of 40000 means no income reaches the final bracket here.

income = 9999
upperBounds = [10000]
ratesBps = [750, 2500]
tax = 749

The exact numerator is 7,499,250; rounding occurs once after division by 10,000.

income = 0
upperBounds = []
ratesBps = [10000]
tax = 0

Hint: Track the previous boundary

For each rate, intersect its bracket interval with [0, income) and add only that slice to the numerator.

Discussion Requirements

1. Explain why applying the highest reached rate to all income is not a marginal-bracket calculation.
2. Show how exclusive boundaries avoid double-counting income at an exact cutoff.
3. Explain why rounding once can differ from rounding each bracket independently.
4. State how the scan can stop after the bracket containing income.

Calculate Tax from Progressive Brackets

Implement calculateProgressiveTax(income, upperBounds, ratesBps) -> tax.

income is a nonnegative integer number of minor currency units. ratesBps holds one marginal rate per tax bracket in basis points, where 10,000 basis points means 100%. upperBounds holds the exclusive upper income boundary of every bracket except the final open-ended one.

If ratesBps.length == m, then upperBounds.length == m - 1 and the brackets are:

• bracket 0: [0, upperBounds[0]) when m > 1;
• bracket i: [upperBounds[i - 1], upperBounds[i]) for each interior bracket;
• bracket m - 1: [upperBounds[m - 2], infinity) when m > 1;
• when m == 1, the single rate applies to all income.

Only the income slice that falls inside a bracket is taxed at that bracket's rate. Compute the full tax numerator as the sum of slice * rateBps across every bracket, then return floor(totalNumerator / 10,000). Round down exactly once, after summing all brackets; do not round each bracket separately.

Function contract

• income is an integer.
• upperBounds and ratesBps are integer arrays.
• Return one integer tax in minor currency units.
• Do not mutate either input array.

Examples

income      = 50000
upperBounds = [10000, 40000]
ratesBps    = [1000, 2000, 3000]
tax         = 10000

The three taxable slices are 10000, 30000 and 10000, taxed at 10%, 20% and 30%, so the numerator is 10,000,000 + 60,000,000 + 30,000,000 = 100,000,000 and the tax is 10000.

income      = 40000
upperBounds = [10000, 40000]
ratesBps    = [1000, 2000, 3000]
tax         = 7000

Because 40000 is an exclusive boundary, no income reaches the final bracket: the numerator is 10,000,000 + 60,000,000 = 70,000,000.

income      = 9999
upperBounds = [10000]
ratesBps    = [750, 2500]
tax         = 749

The exact numerator is 9999 * 750 = 7,499,250, and the single trailing floor gives 749.

income      = 0
upperBounds = []
ratesBps    = [10000]
tax         = 0

Output semantics

The answer is a single integer, so there is no ordering or tie-breaking ambiguity. Two correct implementations must return the identical value for every input in the domain below.

Hints

1. Carry the previous boundary as you scan: it is the inclusive lower edge of the bracket you are about to charge.
2. Intersect each bracket interval with [0, income) and add only that overlap, so a bracket entirely above income contributes nothing and the scan can stop there.
3. Keep one running numerator in a 64-bit accumulator and divide by 10,000 only after the loop ends.

Approach

A single left-to-right scan is enough. lower starts at 0 and always holds the inclusive lower edge of the bracket about to be charged. For bracket index, the exclusive upper edge is upperBounds[index], except for the last bracket, which is open-ended and can be treated as ending at income. Clamping that edge with min(bound, income) yields the taxable slice upper - lower, which is zero or negative exactly when the bracket starts at or above income -- so the loop breaks as soon as lower >= income, which is why the scan stops after the bracket containing income. Each slice is multiplied by its own rate and added to a single running numerator; the floor division by 10,000 happens once, after the loop. Rounding once is not the same as rounding per bracket: two brackets each contributing a numerator of 5,000 round to 0 + 0 individually but to 1 when summed first. The numerator is bounded by income * 10,000 = 1e15, which overflows 32-bit arithmetic, so Java uses long and C++ uses long long; the value stays below 2^53, so a JavaScript Number remains exact. Neither input array is written to, so the inputs are left unmutated.

• Time complexity: O(m), where m = ratesBps.length; the scan stops early once the running lower edge reaches income
• Space complexity: O(1) auxiliary space