0865MediumArrayMathTwo PointersBinary SearchSortingNumber Theory

Nudging Readings onto Prime Values

Tracked in this browser only

Trains the technique from

LeetCode 3896Minimum Operations to Transform Array into Alternating Prime

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 gauge log is given as nums. One nudge raises or lowers a single reading by one, and a reading may be nudged as often as needed but must stay at least 2.

The log is clean when every reading is a prime number. Return the fewest nudges that leave the log clean.

Examples

Example 1

Input: nums = [8, 9, 10]
Output: 4

The reading 8 sits one away from 7, the reading 9 sits two away from 7 and from 11, and the reading 10 sits one away from 11, giving 1 + 2 + 1 nudges.

Example 2

Input: nums = [1]
Output: 1

A reading may not drop below 2, and 1 is not prime, so the single nudge raises it to 2.

Example 3

Input: nums = [24, 25, 26, 27, 28]
Output: 9

The nearest primes are 23 for both 24 and 25, then 29 for 28, and 26 and 27 each sit three away from the nearer of 23 and 29.

Constraints

1 <= nums.length <= 10^5
1 <= nums[i] <= 100000

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 nudges_to_clean(nums: list[int]) -> int:

Java

public long nudgesToClean(int[] nums)

The intended approach

Time O(V log log V + n) for a value ceiling V, with the sieve and the two sweeps done once.Space O(V) for the sieve and the two nearest-prime tables.

Each reading is settled on its own, since nudging one never affects another, so the answer is the distance from each reading to the prime nearest it, added up. Sieve the primes once up to a little past the largest reading a log may hold, then sweep that range twice to record, for every value, the nearest prime at or below it and the nearest at or above it. A reading's cost is the smaller of the two gaps, and a reading below 2 must climb to 2.

Pythonentry point: nudges_to_clean

def nudges_to_clean(nums):
    top = 0
    for v in nums:
        if v > top:
            top = v
    limit = top + 200
    sieve = [True] * (limit + 1)
    sieve[0] = False
    if limit >= 1:
        sieve[1] = False
    p = 2
    while p * p <= limit:
        if sieve[p]:
            for q in range(p * p, limit + 1, p):
                sieve[q] = False
        p += 1
    below = [-1] * (limit + 1)
    last = -1
    for v in range(limit + 1):
        if sieve[v]:
            last = v
        below[v] = last
    above = [-1] * (limit + 1)
    nxt = -1
    for v in range(limit, -1, -1):
        if sieve[v]:
            nxt = v
        above[v] = nxt
    total = 0
    for v in nums:
        if v < 2:
            total += 2 - v
            continue
        best = None
        if below[v] > 0:
            best = v - below[v]
        if above[v] > 0:
            gap = above[v] - v
            if best is None or gap < best:
                best = gap
        total += best
    return total

The obvious version

For each reading, step outward one value at a time, testing each candidate for primality by trial division, and stop at the first prime found. No sieve and no tables.

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_nudges_to_clean(nums):
    def prime(x):
        if x < 2:
            return False
        d = 2
        while d * d <= x:
            if x % d == 0:
                return False
            d += 1
        return True

    total = 0
    for v in nums:
        step = 0
        while True:
            if v - step >= 2 and prime(v - step):
                break
            if prime(v + step):
                break
            step += 1
        total += step
    return total

How this problem was checked

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