Home » Interview coding problems/challenges

# Minimum Time to Display N Character

**Minimum Time to Display N Character**: This is a standard interview problem which can be featured in any interview rounds.

Submitted by Radib Kar, on June 10, 2020

**Problem statement:**

You need to display * N* similar characters on a screen. You are allowed to do three types of operation each time.

- You can insert a character,
- You can delete the last character
- You can copy and paste all displayed characters. After copy operation count of total written character will become twice.

All the operations are assigned different times.

- Time for insertion is
**X** - Time for deletion is
**Y** - Time for copy, paste is
**Z**

You need to output **minimum time to display N characters on the screen** using these operations.

**Input:**

The first line of input contains an integer * T* denoting the number of test cases. Then

*test cases follow. Each test case contains an integer*

**T***denoting the number of same characters to write on the screen. The next line contains time for insertion, deletion, and copying respectively.*

**N****Output:**

Print the minimum time to display * N* characters on the screen.

**Constraints:**

1 <= T <= 100 1 <= N <= 100 1 <= X, Y, Z <= N

**Example:**

Input: Test case: 2 First test case, N, number of characters to be displayed = 9 Value of X, Y, Z respectively, 1 2 1 N, number of characters to be displayed = 10 Value of X, Y, Z respectively, 2 5 4 Output: minimum time for first test case: 5 minimum time for second test case: 14

**Explanation:**

For the first test case no of character to be displayed is: 9 Time for insertion is 1 Time for deletion is 2 Time for copy paste is 1 Say the similar character is 'a' So the best way is Insert two character Time is 2 Copy paste Total character so far is 4 Total time 3 Copy paste again Total character so far is 8 Total time 4 Insert gain Total character so far is 9 Total time 5 This is the most optimum way we can solve this

**Solution Approach:**

This is a recursive problem

And we have a few possibilities,

- Simply insert
- Copy-paste
- Delete

Now we need to understand the optimal option based on the situation

Say a situation where we need to reach character 13 and we are at character 7 displayed already

Also, Cost of Inserting 6 digits is much higher than one-time copy paste and deleting ( just consider this case, it may not happen always if copy paste option is costly)

So, the question is when the "delete" options is useful

It's useful for such case what I mentioned. So if we formulate the recursion

Say,

* N* = number of characters to be displayed.

So, if * n* is odd only then we need deletion if

*is we even don't need that.*

**n**Now, we have our recursion, so we can write the recursive function. Since there will be many overlapping sub-problems, we can wither use top-down DP or bottom-up DP. I have used memoization in my implementation. As an exercise, you should be able to convert the above recursion to tabulation DP.

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; int dp[101]; int minimum(int a, int b) { return a > b ? b : a; } int my(int cur, int x, int y, int z) { if (cur == 1) { return x; } // meoization, dont compute what's already computed if (dp[cur] != -1) return dp[cur]; if (cur % 2 == 0) { //for even n dp[cur] = minimum(x + my(cur - 1, x, y, z), z + my(cur / 2, x, y, z)); } else { //for odd n dp[cur] = minimum(x + my(cur - 1, x, y, z), z + y + my((cur + 1) / 2, x, y, z)); } return dp[cur]; } int main() { int t, n, item; cout << "enter number of testcase\n"; cin >> t; for (int i = 0; i < t; i++) { cout << "Enter number of characters\n"; cin >> n; int x, y, z; cout << "Insert time for insertion, deletion and copy respectively\n"; cin >> x >> y >> z; for (int i = 0; i <= n; i++) dp[i] = -1; cout << "Minimum time is: " << my(n, x, y, z) << endl; } return 0; }

**Output:**

enter number of testcase 3 Enter number of characters 8 Insert time for insertion, deletion and copy respectively 3 2 5 Minimum time is: 16 Enter number of characters 8 Insert time for insertion, deletion and copy respectively 1 1 3 Minimum time is: 7 Enter number of characters 3 Insert time for insertion, deletion and copy respectively 1 4 6 Minimum time is: 3

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.