Daily Leetcode Question 19/08/2024 - 650. 2 Keys Keyboard

Problem Description:

There is only one character 'A' on the screen of a notepad. You can perform one of two operations on this notepad for each step: Copy All: You can copy all the characters present on the screen (a partial copy is not allowed). Paste: You can paste the characters which are copied last time. Given an integer n, return the minimum number of operations to get the character 'A' exactly n times on the screen.

class Solution:
  def minSteps(self, n: int) -> int:
    def isPrime(num):
      if num <= 1:
        return False
      if num <= 3:
        return True
      if num % 2 == 0 or num % 3 == 0:
        return False
      div = 5
      while div ** 2 <= num:
        if num % div == 0 or num % (div + 2) == 0:
          return False
        div += 6
      return True
      
    if isPrime(n):
      return n
    result = 0
    divisor = 2
    while n > 1:
      while n % divisor == 0:
        result += divisor
        n //= divisor
      divisor += 1
  	return result

Explanation:

The key to solving this question lies in understanding how divisors work. Since we cannot make a partial copy, each copy made must be of a divisor of n.

So this problem reduces to finding prime factors of n to decide what the largest number of letters we can copy each time.

Another slight improvement we can make is to decide if n is prime first, this eliminates unnecessary checks.

To decide if a number is prime, we can start by weeding out the obvious primes/ non primes. Then we go through the divisors of num up to sqrt(num) to decide if num has any prime factors. We return True at the end.

def isPrime(num):
  if num <= 1:
    return False
  if num <= 3:
    return True
  if num % 2 == 0 or num % 3 == 0:
    return False
  prime = 5
  while prime ** 2 <= num:
    if num % prime == 0 or num % (prime + 2) == 0:
      return False
  	prime += 6 # we go up by 6 as we already know num has no factors of 2 or 3.
  return True

if n is prime, then we know it takes n steps to get to n 'A''s.

Otherwise, we progress to find the prime factors of n and add it to the result everytime (since we need that many steps to get to divisor by copy and pasting).

def minSteps(n):
  def isPrime(num): # as above
    pass
  
  if isPrime(n):
    return n
  result = 0
  divisor = 2
  while n > 1:
    while n % divisor == 0:
      result += divisor
      n //= divisor
    divisor += 1
  return result

The time complexity of finding all prime factors of a number is O(sqrt(n)). So both the main function minSteps and helper function isPrime both have time complexity O(sqrt(n)).

The space complexity is O(1).

The full solution can be found near the top of the page.