Jobs

Interviews

Discussions

2 Keys Keyboard

Medium

Asked by:

More companies

134 views

Topics:

Dynamic ProgrammingGreedy Algorithms

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.

Example 1:

Input: n = 3
Output: 3
Explanation: Initially, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.

Example 2:

Input: n = 1
Output: 0

Constraints:

1 <= n <= 1000

Try coding it in LeetCode

2 Keys Keyboard

Medium

Asked by:

134 views

Topics:

Dynamic ProgrammingGreedy Algorithms

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.

Example 1:

Input: n = 3
Output: 3
Explanation: Initially, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.

Example 2:

Input: n = 1
Output: 0

Constraints:

1 <= n <= 1000

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum value of n? Is n guaranteed to be a positive integer?
If n is 1, should I return 0, or is one 'A' considered the starting point and therefore requires no operations?
Are there any specific memory constraints I should be aware of, given the potential size of n?
If it is impossible to obtain n 'A's using only Copy All and Paste operations (e.g., if n is prime), what should I return?
Could you provide a small example with the optimal steps to reach n 'A's, for instance, what would be the optimal steps for n = 6?

Brute Force Solution

Approach

The goal is to reach a specific number of 'A's on the screen using only two operations: copy all and paste. A brute force approach tries every possible combination of copy and paste actions to find the shortest sequence.

Here's how the algorithm would work step-by-step:

Start with just one 'A'.
Consider all possible next actions: either copy the existing 'A's or paste the copied 'A's.
For each of these actions, determine the new number of 'A's on the screen.
Repeat the process of copying and pasting, branching out to explore all possible sequences of actions.
Keep doing this until one of the sequences reaches the desired number of 'A's.
Among all sequences that achieve the desired number, select the one with the fewest steps (copy and paste actions).

Code Implementation

def min_steps_brute_force(target_number): 
    queue = [(1, 0, 0)] # (current_number_of_as, clipboard_number_of_as, steps)

    while queue:
        current_number_of_as, clipboard_number_of_as, steps = queue.pop(0)

        if current_number_of_as == target_number:
            return steps

        # If we exceed target, this is not a valid path
        if current_number_of_as > target_number:
            continue

        # Option 1: Copy all
        # Necessary to explore possibility of copying the current number of A's to the clipboard.
        queue.append((current_number_of_as, current_number_of_as, steps + 1))

        # Option 2: Paste
        # Necessary to explore possibility of pasting from clipboard
        if clipboard_number_of_as > 0:
            queue.append((current_number_of_as + clipboard_number_of_as, clipboard_number_of_as, steps + 1))

    return -1 # Should never happen if target_number >= 1

Big(O) Analysis

Time Complexity

O(2^n) – The provided brute force approach explores all possible combinations of 'copy all' and 'paste' operations. In the worst-case scenario, it essentially builds a binary tree where each node represents a state (number of 'A's) and each branch represents a 'copy all' or 'paste' operation. The depth of this tree can be up to n (the target number of 'A's). Therefore, the number of nodes explored can grow exponentially with n, resulting in a time complexity of O(2^n) because each node branches into two possibilities.

Space Complexity

O(N) – The described brute force approach explores all possible sequences of copy and paste actions, potentially using a recursion tree or queue to manage the exploration. The maximum depth of this tree or queue can be proportional to the target number of 'A's, which is represented by N. Therefore, in the worst-case scenario, the auxiliary space used for storing the states of the search process (e.g., the number of 'A's and the current number of steps) could grow linearly with N. Consequently, the space complexity is O(N).

Optimal Solution

Approach

The best way to solve this puzzle is to think about breaking down the number you want to reach into its prime factors. This problem can be solved by finding these prime factors and adding them up, which will lead to the fewest copy and paste actions.

Here's how the algorithm would work step-by-step:

Start with the number 2 because you always start with one 'A'.
Find the smallest number that divides evenly into your target number.
That number is the number of times you will copy all previous A's.
Add that number to your total moves.
Divide your target number by that number. This is your new target.
Repeat this process until your target number is 1. That means you are done.
The total moves you've added up is the minimum number of operations required.

Code Implementation

def calculate_min_steps(target_number: int) -> int:
    min_operations = 0
    divisor = 2

    while target_number > 1:
        # Find the smallest factor; represents copy+paste amount.
        while target_number % divisor == 0:
            min_operations += divisor

            # Reduce the target for the next iteration.
            target_number //= divisor

        divisor += 1

    return min_operations

Big(O) Analysis

Time Complexity

O(sqrt(n)) – The algorithm iterates to find the smallest prime factor of the target number n. In the worst-case scenario, we may need to check divisibility from 2 up to the square root of n to find that smallest factor. The while loop continues to reduce n by dividing it by its smallest prime factor until n becomes 1. Therefore, the dominant operation is finding the prime factors which takes at most sqrt(n) in the worst case.

Space Complexity

O(1) – The provided plain English explanation describes an iterative process that modifies the target number in place and accumulates the total moves in a single variable. It doesn't mention any auxiliary data structures such as lists, hash maps, or arrays. The algorithm uses a constant amount of extra memory, regardless of the input number N. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
n = 1	Return 0 because we start with one 'A' already.
n is prime	The only way to achieve a prime number of 'A's is by copying and pasting one 'A' at a time, resulting in n operations.
n is a power of 2	This case represents repeated doubling, which can be optimized, resulting in log2(n) copy operations.
n is a large composite number	The solution needs to efficiently find the prime factorization of n to minimize operations.
Integer overflow (n is too large)	Ensure the algorithm and data types used (if applicable) can handle the largest possible input without overflowing.
n = 0 or negative	Return 0 because it's not possible to get negative or zero 'A's with these operations, or throw an IllegalArgumentException.
n has only small prime factors (e.g., only 2s and 3s)	Test that the solution correctly minimizes operations by finding and factoring out those numbers correctly.
n is a perfect square	The algorithm should identify the square root and determine copy/paste operations based on that factor.

n = 1

How to Handle:

Return 0 because we start with one 'A' already.

n is prime

How to Handle:

The only way to achieve a prime number of 'A's is by copying and pasting one 'A' at a time, resulting in n operations.

n is a power of 2

How to Handle:

This case represents repeated doubling, which can be optimized, resulting in log2(n) copy operations.

n is a large composite number

How to Handle:

The solution needs to efficiently find the prime factorization of n to minimize operations.

Integer overflow (n is too large)

How to Handle:

Ensure the algorithm and data types used (if applicable) can handle the largest possible input without overflowing.

n = 0 or negative

How to Handle:

Return 0 because it's not possible to get negative or zero 'A's with these operations, or throw an IllegalArgumentException.

n has only small prime factors (e.g., only 2s and 3s)

How to Handle:

Test that the solution correctly minimizes operations by finding and factoring out those numbers correctly.

n is a perfect square

How to Handle:

The algorithm should identify the square root and determine copy/paste operations based on that factor.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum value of n? Is n guaranteed to be a positive integer?
If n is 1, should I return 0, or is one 'A' considered the starting point and therefore requires no operations?
Are there any specific memory constraints I should be aware of, given the potential size of n?
If it is impossible to obtain n 'A's using only Copy All and Paste operations (e.g., if n is prime), what should I return?
Could you provide a small example with the optimal steps to reach n 'A's, for instance, what would be the optimal steps for n = 6?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with just one 'A'.
Consider all possible next actions: either copy the existing 'A's or paste the copied 'A's.
For each of these actions, determine the new number of 'A's on the screen.
Repeat the process of copying and pasting, branching out to explore all possible sequences of actions.
Keep doing this until one of the sequences reaches the desired number of 'A's.
Among all sequences that achieve the desired number, select the one with the fewest steps (copy and paste actions).

Code Implementation

def min_steps_brute_force(target_number): 
    queue = [(1, 0, 0)] # (current_number_of_as, clipboard_number_of_as, steps)

    while queue:
        current_number_of_as, clipboard_number_of_as, steps = queue.pop(0)

        if current_number_of_as == target_number:
            return steps

        # If we exceed target, this is not a valid path
        if current_number_of_as > target_number:
            continue

        # Option 1: Copy all
        # Necessary to explore possibility of copying the current number of A's to the clipboard.
        queue.append((current_number_of_as, current_number_of_as, steps + 1))

        # Option 2: Paste
        # Necessary to explore possibility of pasting from clipboard
        if clipboard_number_of_as > 0:
            queue.append((current_number_of_as + clipboard_number_of_as, clipboard_number_of_as, steps + 1))

    return -1 # Should never happen if target_number >= 1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the number 2 because you always start with one 'A'.
Find the smallest number that divides evenly into your target number.
That number is the number of times you will copy all previous A's.
Add that number to your total moves.
Divide your target number by that number. This is your new target.
Repeat this process until your target number is 1. That means you are done.
The total moves you've added up is the minimum number of operations required.

Code Implementation

def calculate_min_steps(target_number: int) -> int:
    min_operations = 0
    divisor = 2

    while target_number > 1:
        # Find the smallest factor; represents copy+paste amount.
        while target_number % divisor == 0:
            min_operations += divisor

            # Reduce the target for the next iteration.
            target_number //= divisor

        divisor += 1

    return min_operations

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 1	Return 0 because we start with one 'A' already.
n is prime	The only way to achieve a prime number of 'A's is by copying and pasting one 'A' at a time, resulting in n operations.
n is a power of 2	This case represents repeated doubling, which can be optimized, resulting in log2(n) copy operations.
n is a large composite number	The solution needs to efficiently find the prime factorization of n to minimize operations.
Integer overflow (n is too large)	Ensure the algorithm and data types used (if applicable) can handle the largest possible input without overflowing.
n = 0 or negative	Return 0 because it's not possible to get negative or zero 'A's with these operations, or throw an IllegalArgumentException.
n has only small prime factors (e.g., only 2s and 3s)	Test that the solution correctly minimizes operations by finding and factoring out those numbers correctly.
n is a perfect square	The algorithm should identify the square root and determine copy/paste operations based on that factor.

n = 1

How to Handle:

Return 0 because we start with one 'A' already.

n is prime

How to Handle:

The only way to achieve a prime number of 'A's is by copying and pasting one 'A' at a time, resulting in n operations.

n is a power of 2

How to Handle:

This case represents repeated doubling, which can be optimized, resulting in log2(n) copy operations.

n is a large composite number

How to Handle:

The solution needs to efficiently find the prime factorization of n to minimize operations.

Integer overflow (n is too large)

How to Handle:

Ensure the algorithm and data types used (if applicable) can handle the largest possible input without overflowing.

n = 0 or negative

How to Handle:

Return 0 because it's not possible to get negative or zero 'A's with these operations, or throw an IllegalArgumentException.

n has only small prime factors (e.g., only 2s and 3s)

How to Handle:

Test that the solution correctly minimizes operations by finding and factoring out those numbers correctly.

n is a perfect square

How to Handle:

The algorithm should identify the square root and determine copy/paste operations based on that factor.