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_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".
Input: N: 33 X: 12 Y: 10 Output: -1 Input: N: 36 X: 10 Y: 2 Output: 6 (10*3+2*3)
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,
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.
Converting the recursion into DP: