Abstract / Summary

Given a number, repeatedly subtract the largest possible prime less than or equal to the current value until reaching zero and return the count of subtractions.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 56% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Greedy
• Math
• Number Theory

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The primeSubOperation method determines whether a list of integers can be transformed into a strictly increasing sequence by optionally subtracting a single prime number from each element, starting from the end of the list and moving toward the front. The algorithm works in-place, mutating the input list as it proceeds, and returns a Boolean indicating success or failure.

Key Steps

The core logic consists of three distinct phases that repeat for each element except the last one.

Reverse Traversal

The method iterates from the second-last index down to zero, ensuring that later elements are already in a valid state before earlier ones are processed.

for i in range(len(nums) - 2, -1, -1):

Early Acceptance When Already Ordered

If the current element is already smaller than its right neighbor, no modification is required and the loop proceeds to the next index.

if nums[i + 1] > nums[i]:
    continue

Searching for a Suitable Prime

When the ordering condition fails, the algorithm computes the difference between the current element and its neighbor. It then scans for the smallest prime p that, when subtracted, makes the current element strictly less than the neighbor.

diff = nums[i] - nums[i + 1]
adjusted = False
for p in range(max(2, diff + 1), nums[i]):

Prime Verification

Inside the prime search loop, a nested loop checks whether p is prime by testing divisibility up to the square root of p. The inner loop exits early both when a divisor is found and when the square of the divisor exceeds p.

isprime = True
for j in range(2, p):
    if j * j > p:
        break
    if p % j == 0:
        isprime = False
        break

Applying the Adjustment

When a prime passes the test, the algorithm subtracts it from the current element, marks the adjustment as performed, and breaks out of the prime search loop.

if isprime:
    adjusted = True
    nums[i] -= p
    break

Failure Path

If the loop exhausts all candidate primes without finding a suitable one, the method returns False, indicating that the required strictly increasing order cannot be achieved.

if not adjusted:
    return False

Successful Completion

When every element either required no change or was successfully adjusted, the method reaches the end of the outer loop and returns True.

return True

Edge Cases Handled

The implementation gracefully addresses several boundary conditions:

• Already Increasing Suffix - When a suffix of the list is already strictly increasing, the early-continue check skips unnecessary work for those positions.
• Zero or Negative Difference - The diff calculation may yield zero or a negative value; the max(2, diff + 1) expression ensures that the prime search starts at the smallest valid prime (2) regardless of the sign of diff.
• Small Elements - If nums[i] is less than or equal to 2, the range for candidate primes becomes empty, causing the adjusted flag to remain False and the method to return False promptly.
• No Viable Prime - When the current element is only marginally larger than its neighbor and no prime less than the element can produce a smaller value, the algorithm detects the impossibility and exits early.
• Single-Element Input - With a list length of one, the outer loop never executes, and the method returns True by default, correctly reflecting that a single element is trivially strictly increasing.

Performance Optimizations

The code incorporates several techniques that reduce unnecessary computation:

• Reverse Order Processing - By fixing the rightmost elements first, the algorithm avoids revisiting elements after they have been adjusted, eliminating the need for additional passes.
• Early Loop Exit on Ordering - The continue statement for already ordered pairs prevents the expensive prime search when it is not required.
• Bounded Prime Search - The search range for candidate primes is limited to values between max(2, diff + 1) and nums[i] - 1. This prevents testing primes that could never satisfy the ordering constraint.
• Square-Root Early Break - Within the prime verification loop, the condition if j * j > p: break stops divisor checks as soon as the square of the divisor exceeds the candidate, halving the number of iterations for larger primes.
• Immediate Break After Successful Adjustment - Once a suitable prime is found, the algorithm breaks out of both the prime search and the inner divisor loop, avoiding further unnecessary checks.

Imagine you have a long row of building blocks with different heights. The goal is to make sure every single block is shorter than the one that comes after it to create a perfect staircase. To do this, you look at the blocks starting from the end and moving toward the beginning.

When you check two blocks next to each other, you want to make sure the left one is already smaller than the right one. If it is already smaller, you just move on to the next pair.

If the left block is too tall or the same height as the neighbor, you need to shrink it. You do this by picking a special number called a prime number and subtracting it from the height of your block. A prime number is a number that cannot be made by multiplying other smaller numbers together, like two, three, five, or seven.

You search for the smallest prime number that will make your current block just a tiny bit shorter than the one on its right. If you can find such a number, you shrink the block and move forward. If you get stuck and cannot find a prime number that makes the block short enough to fit the pattern, the staircase cannot be built correctly. You keep doing this until every block is in order and you have a beautiful, sloping staircase.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java			Python	TS
	WalkCCC	C++		Java			Python
	leetcode.ca	C++	JS	Java		Go	Python	TS
	Progiez	C++		Java			Python
github	charles-wangkai			Java
	fsq	C++
	JoshCrozier		JS
	Shamik07				Dart
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
Shamik07	Dart
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality