Calculate Amount Paid in Taxes - Practice Coding Problems

Calculate Amount Paid in Taxes - Problem

Array Simulation Easy

You are given a 0-indexed 2D integer array brackets where brackets[i] = [upper_i, percent_i] means that the ith tax bracket has an upper bound of upper_i and is taxed at a rate of percent_i. The brackets are sorted by upper bound (i.e. upper_i-1 < upper_i for 0 < i < brackets.length).

Tax is calculated as follows:

The first upper₀ dollars earned are taxed at a rate of percent₀.
The next upper₁ - upper₀ dollars earned are taxed at a rate of percent₁.
The next upper₂ - upper₁ dollars earned are taxed at a rate of percent₂.
And so on.

You are given an integer income representing the amount of money you earned. Return the amount of money that you have to pay in taxes. Note: Answers within 10^-5 of the actual answer will be accepted.

Input & Output

Example 1 — Basic Progressive Tax

$ Input: brackets = [[3,50],[7,10],[20,25]], income = 10

› Output: 2.65

💡 Note: First $3 taxed at 50%: 3 × 0.5 = 1.5. Next $4 (income 4-7) taxed at 10%: 4 × 0.1 = 0.4. Last $3 (income 8-10) taxed at 25%: 3 × 0.25 = 0.75. Total: 1.5 + 0.4 + 0.75 = 2.65

Example 2 — Income Below Second Bracket

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

› Output: 0.25

💡 Note: First $1 taxed at 0%: 1 × 0.0 = 0. Next $1 (income $2) taxed at 25%: 1 × 0.25 = 0.25. Total: 0 + 0.25 = 0.25

Example 3 — Single Tax Bracket

$ Input: brackets = [[2,3]], income = 2

› Output: 0.06

💡 Note: Entire income of $2 falls in first bracket taxed at 3%: 2 × 0.03 = 0.06

Constraints

1 ≤ brackets.length ≤ 100
1 ≤ upper_i ≤ 1000
0 ≤ percent_i ≤ 100
0 ≤ income ≤ 1000
upper_i is sorted in ascending order
All the values of upper_i are unique
The upper bound of the last tax bracket is greater than or equal to income

Visualization

Tap to expand

Understanding the Visualization

Input

Tax brackets with upper bounds and rates, plus total income

Process

Divide income across brackets and apply corresponding tax rates

Output

Total tax amount calculated from all applicable brackets

Key Takeaway

🎯 Key Insight: Process income by bracket ranges, not individual dollars, for efficient O(n) taxation calculation

Asked in

A Amazon 15 M Microsoft 8

The key insight is to process income by tax brackets rather than dollar by dollar. Instead of checking each individual dollar, calculate how much income falls into each bracket range and apply the tax rate to that entire amount. Best approach processes each bracket once in O(n) time, where n is the number of brackets. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Dollar by Dollar	O(income × brackets)	O(1)	Calculate tax for each individual dollar by finding which bracket it belongs to
Optimized - Process by Brackets	O(n)	O(1)	Process each tax bracket as a whole, calculating tax for income ranges efficiently

Brute Force - Dollar by Dollar — Algorithm Steps

Step 1: For each dollar from 1 to income
Step 2: Find which bracket this dollar falls into
Step 3: Add the tax rate for that bracket to total tax

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Each Dollar

Iterate through dollars 1 to income

Find Bracket

For each dollar, find which tax bracket it belongs to

Apply Tax Rate

Add the corresponding tax rate to total

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

double solution(int brackets[][2], int bracketCount, int income) {
    double totalTax = 0.0;
    
    for (int dollar = 1; dollar <= income; dollar++) {
        // Find which bracket this dollar falls into
        for (int i = 0; i < bracketCount; i++) {
            if (dollar <= brackets[i][0]) {
                totalTax += brackets[i][1] / 100.0;
                break;
            }
        }
    }
    
    return totalTax;
}

int main() {
    int brackets[100][2];
    int bracketCount = 0;
    int income;
    
    // Simple parsing for brackets - assumes format [[a,b],[c,d]]
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    char* ptr = line + 1; // Skip first '['
    while (*ptr != '\0' && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            brackets[bracketCount][0] = atoi(ptr);
            while (*ptr != ',') ptr++;
            ptr++;
            brackets[bracketCount][1] = atoi(ptr);
            bracketCount++;
            while (*ptr != ']') ptr++;
            ptr++;
        } else {
            ptr++;
        }
    }
    
    scanf("%d", &income);
    
    double result = solution(brackets, bracketCount, income);
    printf("%f\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(income × brackets)

For each of 'income' dollars, we search through all brackets to find the right tax rate

✓ Linear Growth

Space Complexity

O(1)

Only using a few variables to track current dollar and total tax

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Dollar by Dollar — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler