GeeksforGeeks App
Open App
Browser
Continue

# Minimum time to write characters using insert, delete and copy operation

We need to write N same characters on a screen and each time we can insert a character, delete the last character and copy and paste all written characters i.e. after copy operation count of total written character will become twice. Now we are given time for insertion, deletion and copying. We need to output minimum time to write N characters on the screen using these operations.

Examples:

```Input : N = 9
insert time = 1
removal time = 2
copy time = 1
Output : 5
N character can be written on screen in 5 time units as shown below,
insert a character
characters = 1  total time = 1
again insert character
characters = 2  total time = 2
copy characters
characters = 4  total time = 3
copy characters
characters = 8  total time = 4
insert character
characters = 9  total time = 5```
Recommended Practice

We can solve this problem using dynamic programming. We can observe a pattern after solving some examples by hand that for writing each character we have two choices either get it by inserting or get it by copying, whichever takes less time. Now writing relation accordingly,
Let dp[i] be the optimal time to write i characters on screen then,

```If i is even then,
dp[i] = min((dp[i-1] + insert_time),
(dp[i/2] + copy_time))
Else (If i is odd)
dp[i] = min(dp[i-1] + insert_time),
(dp[(i+1)/2] + copy_time + removal_time)```

In the case of odd, removal time is added because when (i+1)/2 characters will be copied one extra character will be on the screen which needs to be removed.

## C++

 `// C++ program to write characters in``// minimum time by inserting, removing``// and copying operation``#include ``using` `namespace` `std;` `//  method returns minimum time to write``// 'N' characters``int` `minTimeForWritingChars(``int` `N, ``int` `insert,``                       ``int` `remove``, ``int` `copy)``{``    ``if` `(N == 0)``       ``return` `0;``    ``if` `(N == 1)``       ``return` `insert;` `    ``//  declare dp array and initialize with zero``    ``int` `dp[N + 1];``    ``memset``(dp, 0, ``sizeof``(dp));` `    ``// first char will always take insertion time``    ``dp[1] = insert;` `    ``//  loop for 'N' number of times``    ``for` `(``int` `i = 2; i <= N; i++)``    ``{``        ``/*  if current char count is even then``            ``choose minimum from result for (i-1)``            ``chars and time for insertion and``            ``result for half of chars and time``            ``for copy  */``        ``if` `(i % 2 == 0)``            ``dp[i] = min(dp[i-1] + insert,``                        ``dp[i/2] + copy);` `        ``/*  if current char count is odd then``            ``choose minimum from``            ``result for (i-1) chars and time for``            ``insertion and``            ``result for half of chars and time for``            ``copy and one extra character deletion*/``        ``else``            ``dp[i] = min(dp[i-1] + insert,``                        ``dp[(i+1)/2] + copy + ``remove``);``    ``}``    ``return` `dp[N];``}` `// Driver code``int` `main()``{``    ``int` `N = 9;``    ``int` `insert = 1, ``remove` `= 2, copy = 1;``    ``cout << minTimeForWritingChars(N, insert,``                                ``remove``, copy);``    ``return` `0;``}`

## Java

 `// Java program to write characters in``// minimum time by inserting, removing``// and copying operation` `public` `class` `GFG{``    ` `    ``// method returns minimum time to write``    ``// 'N' characters``    ``static` `int` `minTimeForWritingChars(``int` `N, ``int` `insert,``                                      ``int` `remove, ``int` `copy)``    ``{``        ``if` `(N == ``0``)``        ``return` `0``;``        ``if` `(N == ``1``)``        ``return` `insert;``    ` `        ``// declare dp array and initialize with zero``        ``int` `dp[] = ``new` `int` `[N + ``1``];``        ` `          ``// first char will always take insertion time``          ``dp[``1``] = insert;``    ` `        ``// loop for 'N' number of times``        ``for` `(``int` `i = ``2``; i <= N; i++)``        ``{``            ``/* if current char count is even then``                ``choose minimum from result for (i-1)``                ``chars and time for insertion and``                ``result for half of chars and time``                ``for copy */``            ``if` `(i % ``2` `== ``0``)``                ``dp[i] = Math.min(dp[i-``1``] + insert, dp[i/``2``] + copy);``    ` `            ``/* if current char count is odd then``                ``choose minimum from``                ``result for (i-1) chars and time for``                ``insertion and``                ``result for half of chars and time for``                ``copy and one extra character deletion*/``            ``else``                ``dp[i] = Math.min(dp[i-``1``] + insert,``                                 ``dp[(i+``1``)/``2``] + copy + remove);``        ``}``        ``return` `dp[N];``    ``}``    ` `    ``// Driver code to test above methods``    ``public` `static` `void` `main(String []args)``    ``{``        ``int` `N = ``9``;``        ``int` `insert = ``1``, remove = ``2``, copy = ``1``;``        ``System.out.println(minTimeForWritingChars(N, insert,remove, copy));``    ``}``    ``// This code is contributed by Ryuga``}`

## Python3

 `# Python3 program to write characters in``# minimum time by inserting, removing``# and copying operation` `def` `minTimeForWritingChars(N, insert,``                           ``remove, cpy):``    ` `    ``# method returns minimum time``    ``# to write 'N' characters``    ``if` `N ``=``=` `0``:``        ``return` `0``    ``if` `N ``=``=` `1``:``        ``return` `insert` `    ``# declare dp array and initialize``    ``# with zero``    ``dp ``=` `[``0``] ``*` `(N ``+` `1``)``    ` `    ``# first char will always take insertion time``    ``dp[``1``] ``=` `insert``    ` `    ``# loop for 'N' number of times``    ``for` `i ``in` `range``(``2``, N ``+` `1``):` `        ``# if current char count is even then``        ``# choose minimum from result for (i-1)``        ``# chars and time for insertion and``        ``# result for half of chars and time``        ``# for copy``        ``if` `i ``%` `2` `=``=` `0``:``            ``dp[i] ``=` `min``(dp[i ``-` `1``] ``+` `insert,``                        ``dp[i ``/``/` `2``] ``+` `cpy)` `        ``# if current char count is odd then``        ``# choose minimum from``        ``# result for (i-1) chars and time for``        ``# insertion and``        ``# result for half of chars and time for``        ``# copy and one extra character deletion``        ``else``:``            ``dp[i] ``=` `min``(dp[i ``-` `1``] ``+` `insert,``                        ``dp[(i ``+` `1``) ``/``/` `2``] ``+``                        ``cpy ``+` `remove)` `    ``return` `dp[N]` `# Driver Code``if` `__name__ ``=``=` `"__main__"``:``    ``N ``=` `9``    ``insert ``=` `1``    ``remove ``=` `2``    ``cpy ``=` `1``    ``print``(minTimeForWritingChars(N, insert,``                                 ``remove, cpy))` `# This code is contributed``# by vibhu4agarwal`

## C#

 `// C# program to write characters in``// minimum time by inserting, removing``// and copying operation``using` `System;` `class` `GFG``{``    ``// method returns minimum time to write``    ``// 'N' characters``    ``static` `int` `minTimeForWritingChars(``int` `N, ``int` `insert,``                                        ``int` `remove, ``int` `copy)``    ``{``        ``if` `(N == 0)``            ``return` `0;``        ``if` `(N == 1)``            ``return` `insert;``    ` `        ``// declare dp array and initialize with zero``        ``int``[] dp = ``new` `int``[N + 1];``        ``for``(``int` `i = 0; i < N + 1; i++)``            ``dp[i] = 0;``    ` `          ``// first char will always take insertion time``          ``dp[1] = insert;``      ` `        ``// loop for 'N' number of times``        ``for` `(``int` `i = 2; i <= N; i++)``        ``{``            ` `            ``/* if current char count is even then``                ``choose minimum from result for (i-1)``                ``chars and time for insertion and``                ``result for half of chars and time``                ``for copy */``            ``if` `(i % 2 == 0)``                ``dp[i] = Math.Min(dp[i - 1] + insert,``                            ``dp[i / 2] + copy);``    ` `            ``/* if current char count is odd then``                ``choose minimum from``                ``result for (i-1) chars and time for``                ``insertion and``                ``result for half of chars and time for``                ``copy and one extra character deletion*/``            ``else``                ``dp[i] = Math.Min(dp[i - 1] + insert,``                            ``dp[(i + 1) / 2] + copy + remove);``        ``}``        ``return` `dp[N];``    ``}``    ` `    ``// Driver code``    ``static` `void` `Main()``    ``{``        ``int` `N = 9;``        ``int` `insert = 1, remove = 2, copy = 1;``        ``Console.Write(minTimeForWritingChars(N, insert,``                                            ``remove, copy));``    ``}``}` `//This code is contributed by DrRoot_`

## Javascript

 ``

Output

`5`

Time complexity: O(N)
Auxiliary space: O(N).

This article is contributed by Utkarsh Trivedi. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
The text passage describes a problem of finding the minimum time to write N characters on a screen using insert, delete, and copy operations. It provides an example and a dynamic programming solution in multiple programming languages (C++, Java, Python, C#, and JavaScript).

### Content Structure:
- **Problem Description**: Explains the problem of writing N characters using insert, delete, and copy operations.
- **Example**: Provides a specific example with input and output.
- **Solution Explanation**: Describes the dynamic programming approach to solve the problem.
- **Code Implementations**: Provides code in C++, Java, Python, C#, and JavaScript.

### Analysis:
single_question_with_answer

- **reasoning**:
  - the passage contains a clear mathematical question: "we need to output minimum time to write n characters on the screen using these operations."
  - the answer to this question is provided in the form of a dynamic programming solution and code implementations in multiple programming languages.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
GeeksforGeeks App
Open App
Browser
Continue

# Minimum time to write characters using insert, delete and copy operation

We need to write N same characters on a screen and each time we can insert a character, delete the last character and copy and paste all written characters i.e. after copy operation count of total written character will become twice. Now we are given time for insertion, deletion and copying. We need to output minimum time to write N characters on the screen using these operations.

Examples:

```Input : N = 9
insert time = 1
removal time = 2
copy time = 1
Output : 5
N character can be written on screen in 5 time units as shown below,
insert a character
characters = 1  total time = 1
again insert character
characters = 2  total time = 2
copy characters
characters = 4  total time = 3
copy characters
characters = 8  total time = 4
insert character
characters = 9  total time = 5```
Recommended Practice

We can solve this problem using dynamic programming. We can observe a pattern after solving some examples by hand that for writing each character we have two choices either get it by inserting or get it by copying, whichever takes less time. Now writing relation accordingly,
Let dp[i] be the optimal time to write i characters on screen then,

```If i is even then,
dp[i] = min((dp[i-1] + insert_time),
(dp[i/2] + copy_time))
Else (If i is odd)
dp[i] = min(dp[i-1] + insert_time),
(dp[(i+1)/2] + copy_time + removal_time)```

In the case of odd, removal time is added because when (i+1)/2 characters will be copied one extra character will be on the screen which needs to be removed.

## C++

 `// C++ program to write characters in``// minimum time by inserting, removing``// and copying operation``#include ``using` `namespace` `std;` `//  method returns minimum time to write``// 'N' characters``int` `minTimeForWritingChars(``int` `N, ``int` `insert,``                       ``int` `remove``, ``int` `copy)``{``    ``if` `(N == 0)``       ``return` `0;``    ``if` `(N == 1)``       ``return` `insert;` `    ``//  declare dp array and initialize with zero``    ``int` `dp[N + 1];``    ``memset``(dp, 0, ``sizeof``(dp));` `    ``// first char will always take insertion time``    ``dp[1] = insert;` `    ``//  loop for 'N' number of times``    ``for` `(``int` `i = 2; i <= N; i++)``    ``{``        ``/*  if current char count is even then``            ``choose minimum from result for (i-1)``            ``chars and time for insertion and``            ``result for half of chars and time``            ``for copy  */``        ``if` `(i % 2 == 0)``            ``dp[i] = min(dp[i-1] + insert,``                        ``dp[i/2] + copy);` `        ``/*  if current char count is odd then``            ``choose minimum from``            ``result for (i-1) chars and time for``            ``insertion and``            ``result for half of chars and time for``            ``copy and one extra character deletion*/``        ``else``            ``dp[i] = min(dp[i-1] + insert,``                        ``dp[(i+1)/2] + copy + ``remove``);``    ``}``    ``return` `dp[N];``}` `// Driver code``int` `main()``{``    ``int` `N = 9;``    ``int` `insert = 1, ``remove` `= 2, copy = 1;``    ``cout << minTimeForWritingChars(N, insert,``                                ``remove``, copy);``    ``return` `0;``}`

## Java

 `// Java program to write characters in``// minimum time by inserting, removing``// and copying operation` `public` `class` `GFG{``    ` `    ``// method returns minimum time to write``    ``// 'N' characters``    ``static` `int` `minTimeForWritingChars(``int` `N, ``int` `insert,``                                      ``int` `remove, ``int` `copy)``    ``{``        ``if` `(N == ``0``)``        ``return` `0``;``        ``if` `(N == ``1``)``        ``return` `insert;``    ` `        ``// declare dp array and initialize with zero``        ``int` `dp[] = ``new` `int` `[N + ``1``];``        ` `          ``// first char will always take insertion time``          ``dp[``1``] = insert;``    ` `        ``// loop for 'N' number of times``        ``for` `(``int` `i = ``2``; i <= N; i++)``        ``{``            ``/* if current char count is even then``                ``choose minimum from result for (i-1)``                ``chars and time for insertion and``                ``result for half of chars and time``                ``for copy */``            ``if` `(i % ``2` `== ``0``)``                ``dp[i] = Math.min(dp[i-``1``] + insert, dp[i/``2``] + copy);``    ` `            ``/* if current char count is odd then``                ``choose minimum from``                ``result for (i-1) chars and time for``                ``insertion and``                ``result for half of chars and time for``                ``copy and one extra character deletion*/``            ``else``                ``dp[i] = Math.min(dp[i-``1``] + insert,``                                 ``dp[(i+``1``)/``2``] + copy + remove);``        ``}``        ``return` `dp[N];``    ``}``    ` `    ``// Driver code to test above methods``    ``public` `static` `void` `main(String []args)``    ``{``        ``int` `N = ``9``;``        ``int` `insert = ``1``, remove = ``2``, copy = ``1``;``        ``System.out.println(minTimeForWritingChars(N, insert,remove, copy));``    ``}``    ``// This code is contributed by Ryuga``}`

## Python3

 `# Python3 program to write characters in``# minimum time by inserting, removing``# and copying operation` `def` `minTimeForWritingChars(N, insert,``                           ``remove, cpy):``    ` `    ``# method returns minimum time``    ``# to write 'N' characters``    ``if` `N ``=``=` `0``:``        ``return` `0``    ``if` `N ``=``=` `1``:``        ``return` `insert` `    ``# declare dp array and initialize``    ``# with zero``    ``dp ``=` `[``0``] ``*` `(N ``+` `1``)``    ` `    ``# first char will always take insertion time``    ``dp[``1``] ``=` `insert``    ` `    ``# loop for 'N' number of times``    ``for` `i ``in` `range``(``2``, N ``+` `1``):` `        ``# if current char count is even then``        ``# choose minimum from result for (i-1)``        ``# chars and time for insertion and``        ``# result for half of chars and time``        ``# for copy``        ``if` `i ``%` `2` `=``=` `0``:``            ``dp[i] ``=` `min``(dp[i ``-` `1``] ``+` `insert,``                        ``dp[i ``/``/` `2``] ``+` `cpy)` `        ``# if current char count is odd then``        ``# choose minimum from``        ``# result for (i-1) chars and time for``        ``# insertion and``        ``# result for half of chars and time for``        ``# copy and one extra character deletion``        ``else``:``            ``dp[i] ``=` `min``(dp[i ``-` `1``] ``+` `insert,``                        ``dp[(i ``+` `1``) ``/``/` `2``] ``+``                        ``cpy ``+` `remove)` `    ``return` `dp[N]` `# Driver Code``if` `__name__ ``=``=` `"__main__"``:``    ``N ``=` `9``    ``insert ``=` `1``    ``remove ``=` `2``    ``cpy ``=` `1``    ``print``(minTimeForWritingChars(N, insert,``                                 ``remove, cpy))` `# This code is contributed``# by vibhu4agarwal`

## C#

 `// C# program to write characters in``// minimum time by inserting, removing``// and copying operation``using` `System;` `class` `GFG``{``    ``// method returns minimum time to write``    ``// 'N' characters``    ``static` `int` `minTimeForWritingChars(``int` `N, ``int` `insert,``                                        ``int` `remove, ``int` `copy)``    ``{``        ``if` `(N == 0)``            ``return` `0;``        ``if` `(N == 1)``            ``return` `insert;``    ` `        ``// declare dp array and initialize with zero``        ``int``[] dp = ``new` `int``[N + 1];``        ``for``(``int` `i = 0; i < N + 1; i++)``            ``dp[i] = 0;``    ` `          ``// first char will always take insertion time``          ``dp[1] = insert;``      ` `        ``// loop for 'N' number of times``        ``for` `(``int` `i = 2; i <= N; i++)``        ``{``            ` `            ``/* if current char count is even then``                ``choose minimum from result for (i-1)``                ``chars and time for insertion and``                ``result for half of chars and time``                ``for copy */``            ``if` `(i % 2 == 0)``                ``dp[i] = Math.Min(dp[i - 1] + insert,``                            ``dp[i / 2] + copy);``    ` `            ``/* if current char count is odd then``                ``choose minimum from``                ``result for (i-1) chars and time for``                ``insertion and``                ``result for half of chars and time for``                ``copy and one extra character deletion*/``            ``else``                ``dp[i] = Math.Min(dp[i - 1] + insert,``                            ``dp[(i + 1) / 2] + copy + remove);``        ``}``        ``return` `dp[N];``    ``}``    ` `    ``// Driver code``    ``static` `void` `Main()``    ``{``        ``int` `N = 9;``        ``int` `insert = 1, remove = 2, copy = 1;``        ``Console.Write(minTimeForWritingChars(N, insert,``                                            ``remove, copy));``    ``}``}` `//This code is contributed by DrRoot_`

## Javascript

 ``

Output

`5`

Time complexity: O(N)
Auxiliary space: O(N).

This article is contributed by Utkarsh Trivedi. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
user
The text passage describes a problem of finding the minimum time to write N characters on a screen using insert, delete, and copy operations. It provides an example and a dynamic programming solution in multiple programming languages (C++, Java, Python, C#, and JavaScript).

### Content Structure:
- **Problem Description**: Explains the problem of writing N characters using insert, delete, and copy operations.
- **Example**: Provides a specific example with input and output.
- **Solution Explanation**: Describes the dynamic programming approach to solve the problem.
- **Code Implementations**: Provides code in C++, Java, Python, C#, and JavaScript.

### Analysis:
TYPE: SINGLE_QUESTION_WITH_ANSWER

- **Reasoning**:
  - The passage contains a clear mathematical question: "We need to output minimum time to write N characters on the screen using these operations."
  - The answer to this question is provided in the form of a dynamic programming solution and code implementations in multiple programming languages.