NeetCode #730LC-650Medium2-D Dynamic Programming
← Back to All Problems#730 · #650 · 2 Keys Keyboard(只有两个键的键盘)
📌 Problem Statement & Constraints
A notepad starts with one
A. Two operations are available: Copy All copies everything currently on screen, and Paste appends the clipboard. Return the minimum number of operations needed to reach exactly n As. Constraints: 1 <= n <= 1000.💡 Core Algorithmic Approaches
- Any strategy builds
nas a product of chunk sizes, where producing a chunk of sizepcostspoperations (one copy plusp - 1pastes). - Therefore the minimum number of operations is the sum of the prime factors of
n, counting multiplicity. - For example
n = 12 = 2 * 2 * 3gives2 + 2 + 3 = 7. - A trial-division factorization computes this in O(sqrt(n)).
💻 Benchmark Python3 Implementation
class Solution:
def minSteps(self, n: int) -> int:
steps = 0
d = 2
while d * d <= n:
while n % d == 0:
steps += d
n //= d
d += 1
if n > 1:
steps += n # a remaining prime factor
return steps⚡ Complexity Deep Dive
⏱️ Time Complexity
O(sqrt(n)): trial division up to the square root of n.
💾 Space Complexity
O(1): a few scalars.
⚠️ Interview Pitfalls & Follow-ups
- Assuming a prime
nneedsn - 1steps: a prime requires one copy plusn - 1pastes, which is exactlynoperations. - Forgetting the leftover prime factor: after the loop,
n > 1is a prime that must be added. - Simulating the operations with a DP: that is O(n^2) and unnecessary; factorization is far faster.
- Special-casing
n == 1: the loop and the leftover check both yield 0 automatically.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.