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.
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.
Print the maximum number of segments the Golden Rod can be cut into.
Print the output of each test case in a separate line.
You do not need to print anything; it has already been taken care of. Just implement the given function.
1 <= T <= 100
1 <= "LEN" <= 10000
1 <= "scaleA", "scaleB", "scaleC" <= 10000
Time Limit: 1 second
2
4
2 1 3
13
1 8 10
4
13
For sample test case 1:
The length of the Golden Rod i.e "LEN" is 4 and "scaleA" is 2, "scaleB" is 1 and "scaleC" is 3, then the different ways to cut Golden Rod into segments are:
Four segments each of length 1 i.e [1, 1, 1, 1].
One segment of length 2 and two segments each of length 1 i.e. [2, 1, 1].
One segment of length 1 and one segments each of length 3 i.e. [1, 3].
Two segments each of length 2 i.e [2, 2].
So, Birbal can cut a maximum of 4 segments of this Golden Rod.
For sample test case 2:
The length of the Golden Rod i.e "LEN" is 13 and "scaleA" is 1, "scaleB" is 8 and "scaleC" is 13, then the different ways to cut Golden Rod into segments are:
Thirteen segments each of length 1 i.e [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1].
One segment of length 8 and 5 segments of length 1 i.e [8, 1, 1, 1, 1, 1].
One segment of length 10 and 3 segments of length 1 i.e [10, 1, 1, 1]
So, Birbal can cut a maximum of 13 segments of this Golden Rod.
2
5
5 3 2
5
5 6 8
2
1
Can you come up with a recurrence relation?
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:
O(3 ^ LEN), where LEN denotes the length of the Golden Rod.
In the worst case at every step, we are making three recursive calls and the maximum depth of the recursion tree can go up to LEN. Hence, the time complexity is O(3 ^ LEN).
O(LEN), where LEN denotes the length of the Golden Rod.
In the worst case, extra space is used by the recursion stack which can go up to a maximum depth of LEN. Hence, the space complexity is O(LEN).
All tags
Sort by
Interview problems
Easy Python Code
def findMaxNumSegements(length, scaleA, scaleB, scaleC):
dp = [float('-inf')] * (length + 1)
dp[0] = 0
for rem in range(1, length + 1):
for i in [scaleA, scaleB, scaleC]:
if rem - i >= 0:
dp[rem] = max(dp[rem], 1 + dp[rem - i])
return dp[length] if dp[length] != float('-inf') else 0
Interview problems
Most Optimal | May Be Difficult to Understand | Give a try
#include <bits/stdc++.h>
int findMaxNumSegements(int len, int scaleA,int scaleB,int scaleC){
vector<int> dp(len+1,0);
for(int scale : {scaleA,scaleB,scaleC}){
for(int currlen=1;currlen<=len;currlen++){
int dontCut = dp[currlen];
int cut = (currlen == scale || (scale <= currlen && dp[currlen-scale]) ? 1 + dp[currlen-scale] : 0 );
dp[currlen] = max(dontCut,cut);
}
}
return dp[len];
}Interview problems
Discussion thread on Interview Problem | King and his Golden Rod
Hey everyone, creating this thread to discuss the interview problem - King and his Golden Rod.
Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): King and his Golden Rod
