Home » Interview coding problems/challenges

# Letter/Blog Writer Coding Problem (using Dynamic Programming)

**Letter/Blog Writer Coding Problem**: In this article, we are going to see how to solve a Letter/Blog Writer Coding Problem efficiently with dynamic programming? And, it can be featured in any interview rounds.

Submitted by Radib Kar, on April 19, 2020

**Problem statement:**

**Shivang** is a blog writer and he is working on two websites simultaneously. He has to write two types of blogs which are:

**Technical blogs for website_1**:of this type can be written in an hour. (**X**will be the input)**X****Fun blogs for website_2**:of this type can be written in an hour. (**Y**will be input)**Y**

You are to help him to save time. Given * N* number of total blogs, print the

**minimum number of hours he needs to put for combination of both the blogs**, so that no time is wasted.

Input: N: number of total blogs X: number of Technical blogs for website_1 per hour Y: number of Fun blogs for website_2 per hour Output: Print the minimum number of hours Shivang needs to write the combination of both the blogs (total N). If it is NOT possible, print "−1".

**Example:**

Input: N: 33 X: 12 Y: 10 Output: -1 Input: N: 36 X: 10 Y: 2 Output: 6 (10*3+2*3)

**Explanation:**

For the first case, No combination is possible that's why output is -1. For the second test case, Possible combinations are 30 technical blogs (3 hours) + 6 fun blogs (3 hours) 20 technical blogs (2 hours) + 16 fun blogs (8 hours) 10 technical blogs (1 hours) + 26 fun blogs (13 hours) 0 technical blogs (0 hours) + 36 fun blogs (18 hours) So, best combination is the first one which takes total 6 hours

**The problem is basically solving equation,**

* aX + bY = N* where we need to find the valid integer coefficients of

*and*

**X***. Return*

**Y****a+b**if there exists such else return

**-1**.

We can find a recursive function for the same too,

Say,

f(n) = minimum hours for n problems f(n) = min(f(n-x) + f(n-y)) if f(n-x), f(n-y) is solved already

We can convert the above recursion to DP.

**Solution Approach:**

Converting the recursion into DP:

1) Create DP[n] to store sub problem results 2) Initiate the DP with -1 except DP[0], DP[0]=0 3) Now in this step we would compute values for DP[i] 4) for i=1 to n if i-x>=0 && we already have solution for i-x,i.e.,DP[i-x]!=-1 DP[i]=DP[i-x]+1; end if if i-y>=0 && we already have solution for i-y,i.e.,DP[i-y]!=-1) if DP[i]!=-1 DP[i]=min(DP[i],DP[i-y]+1); else DP[i]=DP[i-y]+1; End if End if End for 5) Return DP[n]

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; int minimumHour(int n, int x, int y) { int a[n + 1]; a[0] = 0; for (int i = 1; i <= n; i++) a[i] = -1; for (int i = 1; i <= n; i++) { if (i - x >= 0 && a[i - x] != -1) { a[i] = a[i - x] + 1; } if (i - y >= 0 && a[i - y] != -1) { if (a[i] != -1) a[i] = min(a[i], a[i - y] + 1); else a[i] = a[i - y] + 1; } } return a[n]; } int main() { int n, x, y; cout << "Enter total number of blogs, N:\n"; cin >> n; cout << "Enter number of techical blogs, X:\n"; cin >> x; cout << "Enter number of fun blogs, Y:\n"; cin >> y; cout << "Minimum hour to be dedicated: " << minimumHour(n, x, y) << endl; return 0; }

**Output**

RUN 1: Enter total number of blogs, N: 36 Enter number of techical blogs, X: 10 Enter number of fun blogs, Y: 2 Minimum hour to be dedicated: 6 RUN 2: Enter total number of blogs, N: 33 Enter number of techical blogs, X: 12 Enter number of fun blogs, Y: 10 Minimum hour to be dedicated: -1

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.