LC-0650 Medium LeetCode

650. 2 Keys Keyboard

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 59% Topics: Math, Dynamic Programming

Reading material

Math & Geometry 12 min 1-D Dynamic Programming 16 min

Reference solution (spoiler · python)

# Time:  O(sqrt(n))
# Space: O(1)

class Solution(object):
    def minSteps(self, n):
        """
        :type n: int
        :rtype: int
        """
        result = 0
        p = 2
        # the answer is the sum of prime factors
        while p**2 <= n:
            while n % p == 0:
                result += p
                n //= p
            p += 1
        if n > 1:
            result += n
        return result

Solution from kamyu104/LeetCode-Solutions · MIT