0467EasyMathDynamic ProgrammingMemoization

Three-Day Dispatch Ladder

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 courier depot keeps a daily log of how many vans it sent out, numbering days from 0.

The log opens with a quiet day: no vans left the yard on day 0. Exactly one van left on day 1, and exactly one left on day 2. From day 3 onward the depot's rule is fixed: the count for a day is the three counts of the days right before it added together.

Given a day number day, return the number of vans the log shows for that day.

Examples

Example 1

Input: day = 0
Output: 0

Day `0` is the quiet day the log opens with, so nothing left the yard.

Example 2

Input: day = 7
Output: 24

Days `4` through `6` show 4, 7 and 13 vans, and day `7` follows from those three.

Example 3

Input: day = 26
Output: 2555757

The counts climb quickly once the depot's rule takes over, and day `26` is a six-figure count.

Constraints

0 <= day <= 37
The count for the requested day is guaranteed to fit in a signed 32-bit integer, so it is at most 2^31 - 1.

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 vans_dispatched(day: int) -> int:

Java

public int vansDispatched(int day)

The intended approach

Time O(day)Space O(1)

Only the last three counts matter at any point, so hold exactly three numbers and slide them forward one day at a time, replacing the newest with the sum of all three. Answer the three opening days directly from the log's fixed values before the slide begins.

Pythonentry point: vans_dispatched

def vans_dispatched(day):
    # Carry only the three most recent day counts forward.
    # time O(day), space O(1)
    if day == 0:
        return 0
    if day <= 2:
        return 1
    older, middle, latest = 0, 1, 1
    for _ in range(3, day + 1):
        older, middle, latest = middle, latest, older + middle + latest
    return latest

The obvious version

Read the depot's rule literally as a recursion: a day's count is the answer for the three days before it, worked out from scratch each time, bottoming out on the three opening days. No results are cached, so the same day gets recomputed many times over.

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_vans_dispatched(day):
    if day == 0:
        return 0
    if day == 1 or day == 2:
        return 1
    return (bf_vans_dispatched(day - 1)
            + bf_vans_dispatched(day - 2)
            + bf_vans_dispatched(day - 3))

How this problem was checked

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