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: X of this type can be written in an hour. (X will be the input)
• Fun blogs for website_2: Y of this type can be written in an hour. (Y will be input)

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 X and Y. Return 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