Maximum Boxes

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
3 upvotes
Asked in company
Cerner Corporation

Problem statement

You are given 'N' apples and multiple boxes with capacities 'A', 'B' and 'C'. Now, you need to calculate the maximum number of boxes in which you can distribute these apples such that no apple is left and none of the boxes is partially filled.

Example: 
Suppose, you have 7 apples and multiple boxes of capacities 2, 3 and 5.

You can keep these 7 apples in maximum 3 boxes i.e. two boxes of capacity 2 and one box of capacity 3.
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 first line of each test case contains a single integer 'N' denoting the number of apples.

The second line of each test case contains three space-separated integers 'A', 'B', and 'C' denoting the capacity of three types of boxes.
Output format: 
For each test case, return the maximum number of boxes in which you can distribute these 'N' apples.

Print the output of each test case in a separate line.
Note: 
1. If it is impossible to distribute the apples into the boxes, simply return 0. 

2. You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <=  T <= 50
1 <=  N <= 10 ^ 5
1 <= A, B, C <= 10 ^ 4

Time limit: 1 sec
Sample Input 1:
2
5
2 3 5
11
2 3 7
Sample Output 1:
2
5
Explanation for Sample Output 1:
In test case 1, There are 2 ways to distribute 5 apples in boxes with capacity 2, 3 and 5.

2 apples in one box and 3 apples in another box, boxes used: 2 

5 apples in 1 box, box used: 1

Maximum boxes are used in the first way, thus, the answer is 2. 

In test case 2, There are 3 ways to distribute 11 apples in boxes with capacity 2, 3 and 7.

2 apples in four boxes (2 * 4) and 3 apples in 1 box (3 * 1), boxes used: 5

2 apples in 1 box (2 * 1) and 3 apples in 3 boxes( 3 * 3), boxes used: 4

2 apples in 2 boxes (2 * 2) and 7 apples in 1 box (7 * 1), boxes used: 3

Maximum boxes are used in the first way, thus, the answer is 5.
Sample Input 2:
2
4
2 1 1
8
5 6 7
Sample Output 2:
4
0
Explanation for Sample Output 2:
In test case 1, There are 4 apples and boxes with capacity 2, 3 and 5.

Maximum boxes will be used when all the apples are in boxes with capacity 1 and thus maximum boxes used are 4.

In test case 2, There is no way to distribute 8 apples in the boxes with capacity 5, 6 and 7.
Hint

The very first approach can be to try all possible distributions of the apples and maximize the ans among the valid ones.

Approaches (3)
Brute Force
  • The idea is to use recursion to reduce the big problem into several small subproblems.
  • We will call a maximumBoxesHelper function that returns us the maximum boxes.
  • The recursive relation used here is pretty simple, the points to be considered are:
    • If the number of apples is less than the minimum capacity among all the given boxes, we don’t have a way for that.
    • As we have three possible ways and we need to find the maximum count of boxes. We need to make recursive calls for each choice individually, thus, we make 3 recursive calls.
  • Thus, the relation becomes:

    Function(N, A, B, C):
  • Base case: If N is less than min(A, min(B, C))
    • Return 0.
  • Recursive calls:
    • MAX of the following 3 recursive calls:
      • 1 + Function(N - A, A, B, C)
      • 1 + Function(N - B, A, B, C)
      • 1 + Function(N - C, A, B, C)
         
  • The algorithm for the maximumBoxesHelper function will be as follows: 

    Int maximumBoxesHelper( N, A, B, C):
  • If N == 0, return 0.
  • If N is less than the minimum of { A, B and C}
    • return INT_MIN, as there is no possible way.
  • Initialize ans = INT_MIN
  • If N is greater than equal to A:
    • Call, ans = max(ans , 1 + maximumBoxesHelper( N-A, A, B, C).
  • If  N is greater than equal to B:
    • Call, ans = max(ans , 1 + maximumBoxesHelper( N-B, A, B, C).
  • If  N is greater than equal to C:
    • Call, ans = max(ans , 1 + maximumBoxesHelper( N-C, A, B, C).
  • Return ans
  • If ans is negative, it means no such arrangement is possible, so, the ans = 0.
Time Complexity

O(3 ^ H), where ‘H’ is the maximum height of the recursive tree.

 

In the worst case, during each recursive call, the value of N decreases either by ‘A’, ‘B’, or ‘C’. i.e. T(N) = T(N - A) + T(N - B) + T(N - C). Now, the maximum height is reached when the decrease in N is minimum. i.e. N decreases by min(A, B, C).

Space Complexity

O('N' / min('A', ‘B’, ‘C’) , Where ‘N’ is the quantity of apples and ‘A’, ‘B’, ‘C’ are the quantity of boxes.

 

Since extra space will be used by the recursion stack which can go to max depth of N / min(A, B, C).

Code Solution
(100% EXP penalty)
Maximum Boxes
Full screen
Console