Problem statement

https://leetcode.com/problems/2-keys-keyboard/

Solution

Note, that all we can do is to multiply number of symbol by some integer number. So, what actually we need to do is to find factorization with the smallest sum of factors. It can be easily shown that we need factorization upto prime numbers.

Complexity

Time complexity of prime factorization is O(sqrt{n}), space complexity is O(log n) due to recursion.

Code

class Solution:
    def minSteps(self, n):
        if n == 1: return 0
        for i in range(2, int(math.sqrt(n)) + 1):
            if n % i == 0:
                return i + self.minSteps(n//i)
        return n