King and his Golden Rod

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
3 upvotes
Asked in company
Microsoft

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4
2 1 3
13
1 8 10
Sample Output 1:
4
13

Explanation For Sample Output 1:

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.
Sample input 2 :
2
5
5 3 2 
5
5 6 8
Sample Output 2 :
2
1
Hint

Can you come up with a recurrence relation?

Approaches (3)
Brute Force

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.
Time Complexity

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).

Space Complexity

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).

Code Solution
(100% EXP penalty)
King and his Golden Rod
Full screen
Console