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
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 <bits/stdc++.h>using namespace std;Â
// method returns minimum time to write// 'N' charactersint 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 codeint 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 Codeif __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 operationusing 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
<script>    // Javascript program to write characters in    // minimum time by inserting, removing    // and copying operation         // method returns minimum time to write    // 'N' characters    function minTimeForWritingChars(N, insert, remove, copy)    {        if (N == 0)            return 0;        if (N == 1)            return insert;              // declare dp array and initialize with zero        let dp = new Array(N + 1);        for(let 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 (let 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[parseInt(i / 2, 10)] + 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[parseInt((i + 1) / 2, 10)] + copy + remove);        }        return dp[N];    }         let N = 9;    let insert = 1, remove = 2, copy = 1;    document.write(minTimeForWritingChars(N, insert,                                         remove, copy));         // This code is contributed by divyeshrabadiya07.</script> |
Output
5
Time complexity: O(N)Â
Auxiliary space: O(N).Â
This article is contributed by Utkarsh Trivedi. If you like neveropen 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 neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Â
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
