Smallest Missing Non-negative Integer After Operations
Real-world version: The Smallest Reading the Rack Cannot ReachThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def find_smallest_integer(readings: list[int], step: int) -> int:public int findSmallestInteger(int[] readings, int step)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's