# String Manipulation: Given two operations on a character 'A', Copy and Paste, find the minimum number of operations to produce a string of length 'N'

I have a solution to the following question which seems straightforward enough. However, I feel as if I am missing something.

The question: Objective: You have given a character ‘A’ which is already printed. You are allowed to perform only 2 operations –

Copy All – This operation will copy all the printed characters. Paste – This operation will paste all the characters which are already copied. Given a number N, write an algorithm to print character ‘A’ exactly N times with minimum no of operations (either copy all or paste) Example

Character – A
N = 6

Option 1: Copy All – this will copy ‘A’
Paste – output “AA”
Paste – output “AAA”
Paste – output “AAAA”
Paste – output “AAAAA”
Paste – output “AAAAAA”
Total operations – 6

Option 2:
Copy All – this will copy ‘A’
Paste – output “AA”
Paste – output “AAA”
Copy All
Paste – output “AAAAAA”
Total operations – 5

Since with option 2, the task is done in 5 operations. Minimum operations – 5

My code:

# Prime factors, this is just a brute force method, I am aware of better ways, however it is not my concern for this solution.

def prime_factors(number):
i = 2
factors = []
while i * i <= number:
if number % i:
i += 1
else:
number //= i
factors.append(i)
if number > 1:
factors.append(number)
return factors

# Helper function to copy the the current character string into the resultant final string
def copy_characters(character_array, character_to_be_copied, number_of_times, operation_count):
for i in range(number_of_times):
character_array += character_to_be_copied
operation_count += 1
return character_array, operation_count

# Main function containing logic
def copy_paste(character_to_be_copied = "A", number_of_times_to_be_pasted = 0):
character_array = ""
operation_count = 0

# Just some validation
if number_of_times_to_be_pasted <= 0: return "Invalid Number of Times to Be Pasted"
if character_to_be_copied == "": return character_array

# The first copy operation
character_array += character_to_be_copied
operation_count += 1

# Finding prime factors
factors = prime_factors(number_of_times_to_be_pasted)

# This code will cycle through the prime factors to perform the copy paste operations
while factors != []:
character_array, operation_count = copy_characters(character_array,
character_to_be_copied, max(factors) - 1, operation_count)
character_to_be_copied = character_array
factors.remove(max(factors))
if factors != [] : operation_count += 1

#finally return the results
print(character_array, operation_count)

# Note: I am aware that fewer operations would be needed if we consider prime factors as further divisible
# ie., for a large prime number this solution would make as many operations as the prime. However, a solution
# that accounts for it would need to allow for memory of past states, which I do not think this question
# is asking for. Please do correct me if I am wrong. Just trying to improve my programming ability.
def main():
copy_paste("A", 7)

if __name__ == '__main__':
main()


Any feedback would be appreciated. Apologies if the format for the question is wrong, starting out in programming and need to get used to the rules for this site

• The approach is correct. It may be optimized a bit.

• Use the fact that $$\N(p^n) = n(p - 1)\$$. Do not collect identical primes in the list, but just count them.

• Calling max(factors) is a waste of time, for two reasons.

First, the list of prime factors is naturally sorted. The way you build it, smaller factors are discovered, and added to the list, before the larger ones. Use factors[-1].

Second, the order in which you process factors really doesn't matter. This is a bit harder to see; try to prove it.

• Combining the bullets above we can see that the list of factors is not needed at all. Process primes as you discover them.

• The problem doesn't ask for the final string. It only asks the number of operations. It means that you don't need to maintain the character_array. You are only interested in its length, a simple integer. Performing the quite expensive concatenations is another waste of cycles.

• Do not hardcode the second argument to copy_paste. Pass it as a command line parameter, and use sys.argv.

• Side note. If a decomposition of large primes (hence the history of copies) is allowed, the problem becomes much more complicated.

• Thanks a lot, this was very helpful. I can see the improvements now. Now that I think about it, the order does not indeed matter, and there was no need to process the primes separtely. I will rework the solution with these points in mind. Also, the addition chain wiki was very insightful. Oct 16 at 22:01