Last Updated: 12 Jan, 2021
King and his Golden Rod
Moderate
Asked in company
It is New year's eve and King Akbar is very happy. He decides to distribute segments of his Golden Rod of length "LEN" among his subjects.
The Golden Rod can be cut into segments using only 3 special scales: "scaleA", "scaleB" and "scaleC", respectively. These scales are called special because the cut length of the Golden Rod can either be "scaleA", "scaleB" or "scaleC".
For example:
If the length of the Golden Rod i.e "LEN" is 5 and "scaleA" is 1, "scaleB" is 2, and "scaleC" is 3; then the different ways to cut Golden Rod into segments are:
Five segments each of length 1 i.e [1, 1, 1, 1, 1].
One segment of length 2 and three segments each of length 1 i.e. [2, 1, 1, 1].
One segment of length 1 and two segments each of length 2 i.e. [1, 2, 2].
One segment of length 3 and two segments each of length 1 i.e. [3, 1, 1].
One segment of length 3 and one segment of length 2 i.e. [3, 2].
Akbar wants to distribute his Golden Rod among maximum possible subjects. So, he calls Birbal for help.
As Birbal, your task is to determine the number of maximum segments the Golden Rod can be cut into.
Note:
If it is not possible to divide the whole Golden rod into segments then return 0.
Input Format
The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first line of each test case contains a single integer "LEN" denoting the Length of the Golden Rod.
The second line of each test case contains 3 single space-separated integer "scaleA", "scaleB," and "scaleC", repsectivley.
Output Format :
Print the maximum number of segments the Golden Rod can be cut into.
Print the output of each test case in a separate line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= "LEN" <= 10000
1 <= "scaleA", "scaleB", "scaleC" <= 10000
Time Limit: 1 second
Approaches
The idea is to use recursion to reduce the big problem into several small subproblems. For finding the maximum number of segments that the given length can be cut into, we find the number of segments that can be obtained from shorter lengths i.e ‘LEN - scaleA‘ , ‘LEN - scaleB‘ , ‘LEN - scaleC‘. The required answer would be 1 + max( LEN - scaleA, LEN - scaleB, LEN - scaleC ) as one more cut should be needed after this to cut length ‘LEN'.
Algorithm:
- If LEN = 0, we return 0. This is because if the length of Golden Rod is 0, we can not cut it into any further segments.
- If LEN < 0, we return the minimum possible value. This is because a negative length rod can not exist.
- We recursively call findMaxNumSegements(LEN - scaleA , scaleA , scaleB , scaleC) , findMaxNumSegements(LEN - scaleB , scaleA , scaleB , scaleC) and findMaxNumSegements(LEN - scaleC , scaleA , scaleB , scaleC) and 1 + maximum among them will be our answer.
If we draw the recursion tree for the recurrence relation of Approach 1, we can observe that there are a lot of overlapping subproblems.
Since the problem has overlapping subproblems, we can solve it more efficiently using memoization by taking an extra ‘memo’ array of size LEN + 1 to store previously calculated results.
Algorithm:
The algorithm is similar to the previous approach with some additions.
We initialize a memo[LEN +1] array with -1. memo[i] will store the maximum number of Golden Rod segments that can be made.
Before calling the function for any valid length ‘i’, we will check whether we already have a solution corresponding to that length present in the ‘memo’.
- If we already have a solution corresponding to ‘i’, we return that solution i.e memo[i].
- Else, we do recursive calls findMaxNumSegements( LEN - scaleA , scaleA , scaleB , scaleC ) , findMaxNumSegements( LEN - scaleB , scaleA , scaleB , scaleC ) and findMaxNumSegements( LEN - scaleC , scaleA , scaleB , scaleC ) and find the maximum among them. We store the maximum of them + 1 in memo[i] and return it.
- We finally return memo[LEN] as our answer.
Initially, we were breaking the large problem into small subproblems but now, let us look at it differently. The idea is to solve the small problem first and then reach the final answer. Thus we will be using a bottom-up approach now.
Algorithm:
- We initialize a dp[LEN+1] array with 0. dp[i] will store the number of maximum segments made having a length of the rod ‘i’.
- We iterate from i = 1 to i = LEN.
- We initialize 3 variables maxCutScaleA, maxCutScaleB and maxCutScaleC to 0, respectively. Here, maxCutScaleA stores the maximum number of segments that the given length i can be cut into using scaleA (similar for maxcutScaleB and maxCutScaleC).
- If ( i - scaleA ) < 0, then we set maxCutScaleA to minimum possible value. This is because a negative length rod can not exist.
- Else we set maxCutScaleA to dp[i - scaleA]. We repeat the same steps 2 and 3 for maxCutScaleB and maxCutScaleC.
- We then set dp[i] to 1 + maximum of (maxCutScaleA, maxCutScaleB, maxCutScaleC).
- Finally, we return dp[LEN] as our answer.
Similar problems