Show problems as
Classic problem #3896MediumArrayMathTwo PointersBinary SearchSortingNumber Theory

Minimum Operations to Transform Array into Alternating Prime

Real-world version: Nudging Readings onto Prime Values
Tracked in this browser only
Read Minimum Operations to Transform Array into Alternating Prime on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def nudges_to_clean(nums: list[int]) -> int:
Java
public long nudgesToClean(int[] nums)

More on the same topics