1184MediumArrayHash TableMathGreedy

The Smallest Reading the Rack Cannot Reach

Tracked in this browser only

Trains the technique from

LeetCode 2598Smallest Missing Non-negative Integer After Operations

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 rack holds the readings readings. Each reading may be raised or lowered by step, as often as you like and each independently of the others.

Once the changes are made, return the smallest whole number from 0 upwards that is not among the readings.

Examples

Example 1

Input: readings = [0, 1, 2, 3], step = 4
Output: 4

Each reading leaves a different remainder against four, so 0 through 3 can all be reached, and reaching 4 would need a second reading leaving no remainder.

Example 2

Input: readings = [7], step = 5
Output: 0

The single reading leaves a remainder of two against five, so it can never be brought to 0.

Example 3

Input: readings = [0, 0, 1, 1], step = 2
Output: 4

Two readings leave no remainder and two leave one, so 0, 1, 2 and 3 are all reachable and 4 would need a third even reading.

Constraints

1 <= readings.length <= 10^5
1 <= step <= 10^5
-10^9 <= readings[i] <= 10^9

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 find_smallest_integer(readings: list[int], step: int) -> int:

Java

public int findSmallestInteger(int[] readings, int step)

The intended approach

Time O(n) over the readings.Space O(step) for the tally at most.

Raising or lowering by `step` never changes a reading's remainder against `step`, and every number sharing that remainder is reachable, going in either direction as far as needed. So a reading is worth nothing more than its remainder. Tally how many readings carry each remainder. Then walk the whole numbers upwards from nothing: reaching `t` needs one reading whose remainder matches `t`'s, and that reading is then spent and cannot cover anything else. The first `t` whose remainder has no reading left is the answer. The walk cannot run past one more than the number of readings, since each step spends one, so it always finishes.

Pythonentry point: find_smallest_integer

def find_smallest_integer(readings, step):
    tally = {}
    for value in readings:
        rest = value % step
        tally[rest] = tally.get(rest, 0) + 1
    at = 0
    while True:
        rest = at % step
        if tally.get(rest, 0) == 0:
            return at
        tally[rest] -= 1
        at += 1

The obvious version

Walk the whole numbers upwards and, for each one, sweep the readings not yet spent looking for one whose gap to it divides exactly by the step, marking it spent when found. The first number with no such reading left is the answer. Costs the reading count squared.

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_find_smallest_integer(readings, step):
    spent = [False] * len(readings)
    at = 0
    while True:
        found = -1
        for i in range(len(readings)):
            if spent[i]:
                continue
            if (readings[i] - at) % step == 0:
                found = i
                break
        if found < 0:
            return at
        spent[found] = True
        at += 1

How this problem was checked

Reference solution executed against 15 test cases — 15 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