0423MediumBinary SearchBit ManipulationTreeBinary Tree

Counting the Chute Junctions

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 mail room sorts parcels through a chute that splits in two at every junction. The chute is built to a strict pattern: counting the top junction as level 0, every level except the deepest one is filled with junctions, and on the deepest level the junctions are packed against the left with nothing to the right of them.

The layout comes to you as layout, a slot listing padded out to a full triangle. If the chute has h levels then layout has exactly 2^h - 1 slots. Slot 0 holds the top junction, and for any slot i the two slots below it are 2*i + 1 and 2*i + 2. A slot holding a number carries a junction, and that number is the junction's stencilled label. A slot holding null is empty. When the chute has no junctions at all, layout is empty.

Return how many junctions the chute has.

Labels carry no information about position and may repeat, and a junction may be labelled 0. Aim to answer in a number of steps that grows with the square of the level count rather than with the junction count, so reading every slot is more work than the pattern demands.

Examples

Example 1

Input: layout = [1, 2, 3, 4, 5, null, null]
Output: 5

The listing is padded to seven slots for a three-level chute. Slots 0 through 4 carry junctions and the last two are empty.

Example 2

Input: layout = [1, 2, 3, 4, 5, 6, 7]
Output: 7

Every slot of this three-level listing carries a junction, and the deepest level is full.

Example 3

Input: layout = [7]
Output: 1

A single level with a single slot, so the chute has one junction, stencilled 7.

Example 4

Input: layout = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, null, null, null]
Output: 12

Four levels, so the listing is padded to fifteen slots. Twelve of them carry junctions, packed against the left of the deepest level.

Example 5

Input: layout = [0, 0, 0, 0, 0, 0, null]
Output: 6

Six of the seven slots carry junctions, every one of them stencilled 0, and only the final slot is empty.

Constraints

The number of junctions is in the range [0, 5 * 10^4].
0 <= junction label <= 5 * 10^4
layout.length == 0 when there are no junctions, otherwise layout.length == 2^h - 1 for the chute's level count h.
The chute always follows the pattern: only the deepest level may be short, and it is packed to the left.

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 count_nodes(layout: list[int | None]) -> int:

Java

public int countNodes(Integer[] layout)

The intended approach

Time O(h^2) for a chute of h levels, which is O((log n)^2) in the junction count n: at most h steps, each measuring an edge of at most h slots.Space O(1): a handful of integer cursors, no structure built from the input.

Measuring how many levels hang below a slot along its left edge is cheap, and for this pattern it settles which of a junction's two sides is packed solid. Take one step at a time from the top: measure the left edge under the right child. When it comes back one short of the levels still below the current junction, everything on the left is solid, so its size plus the junction itself is added and the walk moves right; otherwise the right side is the solid one, its size plus the junction is added and the walk moves left. The walk takes at most one step per level and each measurement costs at most one level's worth of slot checks.

Pythonentry point: count_nodes

def count_nodes(layout):
    # Walk down one root-to-deepest path. At each step, measure how many levels
    # hang off the right child along its own left edge: if that is one less than
    # the levels still below the current junction, the left side is packed solid
    # and its size is known outright, so bank it and step right; otherwise the
    # right side is the solid one, bank that instead and step left. Each measure
    # costs at most the number of levels, and there are at most that many steps.
    size = len(layout)

    def left_run(start):
        levels = 0
        at = start
        while at < size and layout[at] is not None:
            levels += 1
            at = 2 * at + 1
        return levels

    levels_below = left_run(0)
    if levels_below == 0:
        return 0
    total = 0
    at = 0
    while levels_below > 0:
        if left_run(2 * at + 2) == levels_below - 1:
            total += 1 << (levels_below - 1)
            at = 2 * at + 2
        else:
            total += 1 << (levels_below - 2)
            at = 2 * at + 1
        levels_below -= 1
    return total

The obvious version

Read every slot of the listing and count the ones that are not empty. Linear in the padded listing length, which is up to twice the junction count.

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_count_nodes(layout):
    seen = 0
    for slot in layout:
        if slot is not None:
            seen += 1
    return seen

How this problem was checked

Reference solution executed against 25 test cases — 25 passed
5 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