~/problems / Arrays & hashing / Complexity analysis

The Tax Collector

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

hard assessment 3 levels ~45 min

Level 1 Collect from every house

A tax collector walks down a street of n houses, numbered 1 to n. The rule book is odd: house i pays n // i coins (integer division, rounded down). House 1 pays the most, and every house past the middle pays 1 coin.

Implement total_tax(n: int) -> int: the total number of coins collected from all n houses.

total_tax(5)    # 10: 5 + 2 + 1 + 1 + 1
total_tax(1)    # 1: one house pays 1 // 1
total_tax(10)   # 27: 10 + 5 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1

Constraints: 1 <= n <= 10^4. Read them before you start: 10,000 houses is only 10,000 steps, so a plain loop over every house is fine here.

Level 2 unlocks when level 1 passes.

Level 3 unlocks when level 2 passes.

Topic: Complexity analysis. Big-O from constraints: n = 10^5 means O(n log n); know the Python constant factors.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc