Problem

Submissions

Hints & solutions

Discuss

Cut Into Segments

Moderate

0/80

Average time to solve is 25m

Contributed by

94 upvotes

Asked in companies

Problem statement

You are given an integer ‘N’ denoting the length of the rod. You need to determine the maximum number of segments you can make of this rod provided that each segment should be of the length 'X', 'Y', or 'Z'.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘T’ lines represent the ‘T’ test cases.

The only line of each test case contains 4 integers denoting ‘N’, ’X’, ’Y’, and ‘Z’,  where ‘N’ is the length of the rod and 'X', 'Y', 'Z' are the segments into which a given rod can be cut into.

Output Format:

For each test case, return the maximum number of cut segments from the given rod.

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.

Constraint:

1 <= T <= 50
1 <= N <= 10000
1 <= X, Y, Z <= N

Time Limit: 1 sec

Sample Input 1:

2
7 5 2 2
8 3 3 3

Sample Output 1:

2
0

Explanation For Sample Input 1:

In the first test case, cut it into 2 parts of 5 and 2.

In the second case, there is no way to cut into segments of 3 length only as the length of the rod is less than the given length.

Sample Input 2:

2
7 3 2 2
8 1 4 4

Sample Output 2:

3
8

Explanation For Sample Input 2:

In the first test case, cut it into 3 parts of 3, 2 and 2.

In the second case, cut it into 8 parts of length 1.

Hint 1

Hint 2

Try to calculate by taking all possibilities.

Approaches (2)

Approach 1

Approach 2

Brute Force

The key idea is that no maximum cuts that can be made in the rod of length ‘N’ depend upon Maximum cuts made in shorter length.For ‘n’ length rod ans depends upon 'N’ - ’X’, ’N’ - ’Y’ and ‘N’ - ’Z’ sizes of the rod.

Algorithm:

Create two base case for recursive function such that if length of rod is 0, then return 0. Also add the case if length of rod is less than 0 return infinity.
Recursively call the function on ‘N’ - ’X’, ’N’ - ’Y’ and ‘N’ - ’Z’ length rods.
The answer for ‘N’ length rod is the max of above 3 recursive ‘ANS’ + 1.
If the answer is greater than equal to infinity return 0 as it cannot be cut into rods of length ‘X’ ,’Y’ and ‘Z’. Else return the ‘ANS’.

Time Complexity

O(3^N) where ‘N’ is the length of a given rod.

When ‘X’, ’Y’, ’Z’ equal to 1 then worse case will happen and we recursively call them.

Space Complexity

O(1)

Constant extra space is required.

(100% EXP penalty)

Cut Into Segments

Console