Last Updated: 28 Feb, 2021

Cut Into Segments

Moderate

Asked in companies

Solve now

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

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

Solve now

Approaches

01 Approach

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

Solve now

02 Approach

The key id 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. Since it has overlapping subproblems it could be solved by dp.

Algorithm:

Initialize a ‘DP’ array of size ‘N’ + 1 with -1 and ‘DP[0]’ with 0 as 0 length rod can be cut into 0 segments.
Run a loop ‘i' from 1 to ‘N’.
Check for ‘X’ that 'i' >= ‘X’ (the length of rod is greater than ‘i’) and ‘DP[ i - X]’ != -1 (It means that rod ‘i’ - ’X’ can be cut into segments of ‘X’, ’Y’ and ‘X’ if DP[i - X] != -1 ) then ‘DP[i]’ = max('DP[i]', ‘DP[i - X]’).
Repeat the previous step for ‘Y’ and ‘Z’ also.
If ‘DP[N]’ equals -1 means it cannot be cut into segments hence return 0 else return ‘DP[N]’.

Solve now