⚡Flashcard Drill➔
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

  1. Any strategy builds n as a product of chunk sizes, where producing a chunk of size p costs p operations (one copy plus p - 1 pastes).
  2. Therefore the minimum number of operations is the sum of the prime factors of n, counting multiplicity.
  3. For example n = 12 = 2 * 2 * 3 gives 2 + 2 + 3 = 7.
  4. 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 n needs n - 1 steps: a prime requires one copy plus n - 1 pastes, which is exactly n operations.
  • Forgetting the leftover prime factor: after the loop, n > 1 is 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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems