Q:

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

0

Letter/Blog Writer Coding Problem (using Dynamic Programming)

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

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

interview C++ coding problems/challenges | dynamic programming

This question belongs to these collections

Similar questions


need a help?


find thousands of online teachers now
Given a square matrix of size n x n, find the sum ... >>
<< There is a shop which sells pizza of three differe...