650. Keys Keyboard

📝 Problem Details

• Title: 650. Keys Keyboard
• Link: https://leetcode.com/problems/2-keys-keyboard/
• Difficulty: Medium
• Tags/Categories: Math Dynamic-Programming

💭What Were My Initial Thoughts?

- To minimize the number of operations, consider when to perform multiple pastes versus when to perform a copy/paste operation.
- The problem can be thought of as breaking down `n` into smaller factors and leveraging these factors for repeated pasting.
- If a number can be achieved by multiplying smaller factors, copying and pasting based on these factors minimizes steps.

🤔What Did I Struggle With?

- i could not translate the human intuition into a algorithm during the interview

💡 Explanation of Solution

- **Key Idea:**
    - The problem reduces to breaking down `n` into its prime factors. Each prime factor contributes to the number of steps required.
    - For a factor `f`, the steps required are:
        - `f` operations to paste `f` times (including one copy).
- 
- **Algorithm:**  
    - Start with the smallest factor, `2`.
    - Divide `n` by the current factor as long as it is divisible, adding the factor value to the steps each time.
    - Move to the next factor and repeat until `n` is reduced to 1.
    - The total steps required are the sum of all factors.

- **Why This Works:**
    - Breaking `n` into prime factors ensures we perform the minimum number of copy/paste operations.
    - Larger factors inherently include smaller factors, making this approach optimal.

⌛ Complexity Analysis

Time Complexity: O(sqrt(n))
- each division step reduces n by a factor, and we only iterate up to the square root of n for factorization

Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    int minSteps(int n) {
        if (n == 1) return 0;
        
        int steps = 0;
        int factor = 2;
        
        while (n > 1) {
            while (n % factor == 0) {
                steps += factor;
                n /= factor;
            }
            factor++;
        }
        
        return steps;
    }
};