2 keys keyboard

Math Dynamic Programming

59.3% acceptance

Feb 20, 2026

4406

247

Given n, return minimum operations (Copy All + Paste) to get exactly n 'A's. The answer equals the sum of prime factors of n.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_steps(n: i32) -> i32 {
    let mut n = n;
    let mut result = 0;
    let mut d = 2;
    while n > 1 {
      while n % d == 0 {
        result += d;
        n /= d;
      }
      d += 1;
    }
    result
  }
}