0447EasyTreeDepth-First SearchBinary Search TreeBinary Tree

Auditing a Fare Band in the Register

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A tramway fare machine files the day's takings in a sorted register. Each entry in the register records one fare in pence and hangs two branches beneath it, a lighter branch and a heavier branch. Every fare filed anywhere in an entry's lighter branch is strictly smaller than that entry's own fare, and every fare filed anywhere in its heavier branch is strictly larger. No two entries record the same fare.

The register reaches you as register, which lists the entries one level at a time from the top down and, inside a level, from left to right with the lighter branch before the heavier one. Slot 0 holds the top entry. Reading the listing from the front, each entry takes the next two slots that nothing has taken yet: the first belongs to its lighter branch and the second to its heavier branch. A slot holding null means that branch is empty, and an empty branch takes no slots of its own. null slots at the very end of the listing may be left out.

An auditor is reconciling one fare band. Return the total of every fare in the register that is at least low and at most high, counting both ends of the band. If no fare falls in the band, the total is 0.

Examples

Example 1

Input: register = [32, 15, 47, 8, 23, 39, 55], low = 20, high = 45
Output: 94

The register holds the fares 32, 15, 47, 8, 23, 39 and 55. Of those, 23, 32 and 39 are at least 20 and at most 45, and they come to 94.

Example 2

Input: register = [32, 15, 47, 8, 23, 39, 55], low = 47, high = 100
Output: 102

Two fares, 47 and 55, are at least 47 and at most 100, so the audit line comes to 102.

Example 3

Input: register = [42], low = 1, high = 41
Output: 0

The register holds one fare of 42, which is above the top of the band, so nothing is counted.

Example 4

Input: register = [70, 30, 90, 20, 50, 85, null, null, null, 45], low = 45, high = 85
Output: 250

The fares 45, 50, 70 and 85 all lie inside the band, and together they come to 250.

Constraints

The number of entries in the register is in the range [1, 2 * 10^4].
1 <= fare of an entry <= 10^5
1 <= low <= high <= 10^5
All fares in the register are distinct.
register[0] holds an entry.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def band_total(register: list[int | None], low: int, high: int) -> int:

Java

public int bandTotal(Integer[] register, int low, int high)

The intended approach

Time O(n) in the listing length: the decode reads every slot before the walk starts, and the walk visits each entry at most once.Space O(n) for the two branch tables and the stack.

Decode the listing once into tables of lighter and heavier slot numbers, then walk the register from an explicit stack so that a register filed as one long chain cannot exhaust anything. The filing order pays off at each entry: a fare under the bottom of the band rules out its whole lighter branch, a fare over the top rules out its whole heavier branch, and a fare inside the band is added with both branches still worth opening.

Pythonentry point: band_total

def band_total(register, low, high):
    # One sweep of the listing hands every entry the slot numbers of its lighter
    # and heavier branches, remembering that an empty branch takes no slots. The
    # walk itself then runs off an explicit stack, so a register filed as one long
    # chain cannot overflow anything: at each entry, a fare below the band means
    # nothing in its lighter branch can qualify either, a fare above the band
    # means nothing in its heavier branch can, and a fare inside the band is
    # added and both branches are still worth opening.
    # O(n) time in the listing length, since the listing is decoded in full before
    # the walk starts; O(n) space for the branch tables and the stack.
    size = len(register)
    if size == 0 or register[0] is None:
        return 0
    lighter = [-1] * size
    heavier = [-1] * size
    free = 1
    for idx in range(size):
        if register[idx] is None:
            continue
        if free < size:
            if register[free] is not None:
                lighter[idx] = free
            free += 1
        if free < size:
            if register[free] is not None:
                heavier[idx] = free
            free += 1

    total = 0
    stack = [0]
    while stack:
        idx = stack.pop()
        fare = register[idx]
        if fare < low:
            if heavier[idx] >= 0:
                stack.append(heavier[idx])
            continue
        if fare > high:
            if lighter[idx] >= 0:
                stack.append(lighter[idx])
            continue
        total += fare
        if lighter[idx] >= 0:
            stack.append(lighter[idx])
        if heavier[idx] >= 0:
            stack.append(heavier[idx])
    return total

The obvious version

Ignore the filing order altogether: read straight along the listing and add up every slot that holds a fare inside the band.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_band_total(register, low, high):
    total = 0
    for slot in register:
        if slot is None:
            continue
        if low <= slot <= high:
            total += slot
    return total

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in