Maximize the number of boxes using red and yellow balls
We are given R red balls and Y yellow balls to fill in boxes. We can fill a box using one of the two ways:
- Using A red balls and B yellow balls
- Using B red balls and A yellow balls.
Maximize the number of boxes we can fill.
Note: One ball can belong to only one box
Examples:
Input: R = 10, Y = 12, A = 2, B = 5
Output: 3
Explanation: First and Second box will have 2 Red balls and 5 Yellow Balls. Third box will have 5 Red Balls and 2 Yellow BallsInput: R = 1, Y = 1, A = 2, B = 2
Output: 0
Explanation: 0 box can be filled.
Approach: To solve the problem, follow the below idea:
The problem can be solved by using Ternary Search on the number of times we use the first way to fill a box, that is using A red balls and B yellow balls. We can use ternary search because if we keep on increasing the number of times to fill the box using first way, then the number of ways to fill the box increases initially, reaches the maximum point and then starts decreasing. Therefore, the number of ways to fill the box behaves as a Unimodal function and therefore we can use Ternary Search on it. Let’s say we filled X boxes using A red balls and B yellow balls, so for the remaining (R – A * X) red balls and (Y – B * Y) yellow balls, we can only use the second way to fill the boxes. Now, find the total number of boxes by summing up boxes of both types.
Step-by-step algorithm:
- Declare a function, say getBoxes(R, Y, A, B, mid) to return the number of boxes if we use the first way mid times to fill the boxes.
- Now, declare the range of the number of times we can use the first way to fill the number of boxes.
- Apply ternary search and reduce the search space.
- Finally, iterate over all every value between lo and hi to get the maximum number of boxes one can fill.
Below is the implementation of the algorithm:
C++
#include <bits/stdc++.h> using namespace std; // function to find the total number of boxes if we use the // first way mid times to fill boxes and use the second way // to fill the remaining boxes int getBoxes( int R, int Y, int A, int B, int mid) { // Number of boxes filled using first way int firstWay = mid; // Remaining red balls after filling boxes using first // way int remainingRedBalls = (R - (A * mid)); // Remaining Yellow balls after filling boxes using // second way int remainingYellowBalls = (Y - (B * mid)); // Number of boxes filled using second way int secondWay = min(remainingRedBalls / B, remainingYellowBalls / A); // returning the total number of boxes filled return firstWay + secondWay; } // Function to find the maximum number of boxes int solve( int R, int Y, int A, int B) { // range for the number of times we have used type 1 way // to fill the boxes int lo = 0, hi = min(R / A, Y / B); // ternary search while (hi - lo > 2) { int mid1 = lo + (hi - lo) / 3; int mid2 = hi - (hi - lo) / 3; int res1 = getBoxes(R, Y, A, B, mid1); int res2 = getBoxes(R, Y, A, B, mid2); if (res1 == res2) { lo = mid1; hi = mid2; } else if (res1 < res2) { lo = mid1; } else { hi = mid2; } } int res = 0; while (lo <= hi) { res = max(res, getBoxes(R, Y, A, B, lo)); lo += 1; } return res; } int main() { // Sample Input int R = 10, Y = 12, A = 2, B = 5; cout << solve(R, Y, A, B) << "\n" ; } |
Java
class Main { // Function to find the total number of boxes // using the first way mid times to fill boxes // and using the second way to fill the remaining boxes static int getBoxes( int R, int Y, int A, int B, int mid) { // Number of boxes filled using the first way int firstWay = mid; // Remaining red balls after filling boxes using the first way int remainingRedBalls = (R - (A * mid)); // Remaining yellow balls after filling boxes using the second way int remainingYellowBalls = (Y - (B * mid)); // Number of boxes filled using the second way int secondWay = Math.min(remainingRedBalls / B, remainingYellowBalls / A); // Returning the total number of boxes filled return firstWay + secondWay; } // Function to find the maximum number of boxes static int solve( int R, int Y, int A, int B) { // Range for the number of times we have used the first way // to fill the boxes int lo = 0 , hi = Math.min(R / A, Y / B); // Ternary search while (hi - lo > 2 ) { int mid1 = lo + (hi - lo) / 3 ; int mid2 = hi - (hi - lo) / 3 ; int res1 = getBoxes(R, Y, A, B, mid1); int res2 = getBoxes(R, Y, A, B, mid2); if (res1 == res2) { lo = mid1; hi = mid2; } else if (res1 < res2) { lo = mid1; } else { hi = mid2; } } int res = 0 ; while (lo <= hi) { res = Math.max(res, getBoxes(R, Y, A, B, lo)); lo += 1 ; } return res; } public static void main(String[] args) { // Sample Input int R = 10 , Y = 12 , A = 2 , B = 5 ; System.out.println(solve(R, Y, A, B)); } } // This code is contributed by rambabuguphka |
Python3
# Function to find the total number of boxes if we use the # first way mid times to fill boxes and use the second way # to fill the remaining boxes def get_boxes(R, Y, A, B, mid): # Number of boxes filled using first way first_way = mid # Remaining red balls after filling boxes using first way remaining_red_balls = R - (A * mid) # Remaining Yellow balls after filling boxes using # second way remaining_yellow_balls = Y - (B * mid) # Number of boxes filled using second way second_way = min (remaining_red_balls / / B, remaining_yellow_balls / / A) # Returning the total number of boxes filled return first_way + second_way # Function to find the maximum number of boxes def solve(R, Y, A, B): # Range for the number of times we have used type 1 way # to fill the boxes lo, hi = 0 , min (R / / A, Y / / B) # Ternary search while hi - lo > 2 : mid1 = lo + (hi - lo) / / 3 mid2 = hi - (hi - lo) / / 3 res1 = get_boxes(R, Y, A, B, mid1) res2 = get_boxes(R, Y, A, B, mid2) if res1 = = res2: lo = mid1 hi = mid2 elif res1 < res2: lo = mid1 else : hi = mid2 res = 0 while lo < = hi: res = max (res, get_boxes(R, Y, A, B, lo)) lo + = 1 return res if __name__ = = "__main__" : # Sample Input R, Y, A, B = 10 , 12 , 2 , 5 # Calling the function and printing the result print (solve(R, Y, A, B)) |
C#
using System; public class Program { // function to find the total number of boxes if we use the // first way mid times to fill boxes and use the second way // to fill the remaining boxes static int GetBoxes( int R, int Y, int A, int B, int mid) { // Number of boxes filled using first way int firstWay = mid; // Remaining red balls after filling boxes using first way int remainingRedBalls = R - (A * mid); // Remaining Yellow balls after filling boxes using second way int remainingYellowBalls = Y - (B * mid); // Number of boxes filled using second way int secondWay = Math.Min(remainingRedBalls / B, remainingYellowBalls / A); // returning the total number of boxes filled return firstWay + secondWay; } // Function to find the maximum number of boxes static int Solve( int R, int Y, int A, int B) { // range for the number of times we have used type 1 way // to fill the boxes int lo = 0, hi = Math.Min(R / A, Y / B); // ternary search while (hi - lo > 2) { int mid1 = lo + (hi - lo) / 3; int mid2 = hi - (hi - lo) / 3; int res1 = GetBoxes(R, Y, A, B, mid1); int res2 = GetBoxes(R, Y, A, B, mid2); if (res1 == res2) { lo = mid1; hi = mid2; } else if (res1 < res2) { lo = mid1; } else { hi = mid2; } } int res = 0; while (lo <= hi) { res = Math.Max(res, GetBoxes(R, Y, A, B, lo)); lo += 1; } return res; } public static void Main( string [] args) { // Sample Input int R = 10, Y = 12, A = 2, B = 5; Console.WriteLine(Solve(R, Y, A, B)); } } |
Javascript
// Function to find the total number of boxes if we use the // first way mid times to fill boxes and use the second way // to fill the remaining boxes function getBoxes(R, Y, A, B, mid) { // Number of boxes filled using first way let firstWay = mid; // Remaining red balls after filling boxes using first way let remainingRedBalls = R - (A * mid); // Remaining Yellow balls after filling boxes using second way let remainingYellowBalls = Y - (B * mid); // Number of boxes filled using second way let secondWay = Math.min(Math.floor(remainingRedBalls / B), Math.floor(remainingYellowBalls / A)); // Returning the total number of boxes filled return firstWay + secondWay; } // Function to find the maximum number of boxes function solve(R, Y, A, B) { // Range for the number of times we have used type 1 way to fill the boxes let lo = 0, hi = Math.min(Math.floor(R / A), Math.floor(Y / B)); // Ternary search while (hi - lo > 2) { let mid1 = lo + Math.floor((hi - lo) / 3); let mid2 = hi - Math.floor((hi - lo) / 3); let res1 = getBoxes(R, Y, A, B, mid1); let res2 = getBoxes(R, Y, A, B, mid2); if (res1 === res2) { lo = mid1; hi = mid2; } else if (res1 < res2) { lo = mid1; } else { hi = mid2; } } let res = 0; while (lo <= hi) { res = Math.max(res, getBoxes(R, Y, A, B, lo)); lo += 1; } return res; } // Sample Input let R = 10, Y = 12, A = 2, B = 5; console.log(solve(R, Y, A, B)); |
3
Time Complexity: O(2 * log3(min(R/A, Y/B)), where R is the total number of Red Balls, Y is the total number of Yellow balls and A and B are the number of balls to fill a box.
Auxiliary Space: O(1)