We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

2 Keys Keyboard

Number: 650

Difficulty: Medium

Paid? No

Companies: Meta, Google, Bloomberg, TikTok, Microsoft

Problem Description

We start with a single character 'A' on a notepad and are allowed two operations: Copy All and Paste. The goal is to determine the minimum number of steps needed using these operations to have exactly n 'A's on the screen.

Key Insights

  • The optimal strategy is to use previously computed results to build up to n by breaking n into factors.
  • Every time you copy and then paste, you are effectively multiplying the current count by a factor.
  • The minimum number of operations is the sum of the prime factors of n.
  • When n is prime, the best you can do is copy all and then paste (n-1) times.

Space and Time Complexity

Time Complexity: O(√n) – We iterate up to the square root of n to factorize. Space Complexity: O(1) – Only a few integer variables are needed.

Solution

The approach is to factorize n by checking all possible divisors from 2 upwards. For each divisor d of n, we repeatedly divide n by d and add d to the result (which represents the cost of performing copy and paste operations). If after factorization n is greater than 1, it means n is a prime number and we add n to the result. This greedy method ensures that we are summing the minimal operations as we break down n into its prime components.

Code Solutions

# Python solution for 2 Keys Keyboard problem

def minSteps(n: int) -> int:
    steps = 0  # stores the total number of operations
    factor = 2
    # factorize n starting from 2 to sqrt(n)
    while factor * factor <= n:
        while n % factor == 0:  # if factor divides n
            steps += factor  # add the factor to the step count (1 copy + factor-1 pastes)
            n //= factor  # reduce n by that factor
        factor += 1  # move to the next potential factor
    # if n is still greater than 1, then it's a prime number
    if n > 1:
        steps += n
    return steps

# Example usage:
print(minSteps(3))  # Expected output: 3
← Back to All Questions