|
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 Balls
Input: 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;
int getBoxes(int R, int Y, int A, int B, int mid)
{
int firstWay = mid;
int remainingRedBalls = (R - (A * mid));
int remainingYellowBalls = (Y - (B * mid));
int secondWay = min(remainingRedBalls / B,
remainingYellowBalls / A);
return firstWay + secondWay;
}
int solve(int R, int Y, int A, int B)
{
int lo = 0, hi = min(R / A, Y / B);
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()
{
int R = 10, Y = 12, A = 2, B = 5;
cout << solve(R, Y, A, B) << "\n";
}
|
Java
class Main {
static int getBoxes(int R, int Y, int A, int B, int mid) {
int firstWay = mid;
int remainingRedBalls = (R - (A * mid));
int remainingYellowBalls = (Y - (B * mid));
int secondWay = Math.min(remainingRedBalls / B,
remainingYellowBalls / A);
return firstWay + secondWay;
}
static int solve(int R, int Y, int A, int B) {
int lo = 0, hi = Math.min(R / A, Y / B);
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) {
int R = 10, Y = 12, A = 2, B = 5;
System.out.println(solve(R, Y, A, B));
}
}
|
Python3
def get_boxes(R, Y, A, B, mid):
first_way = mid
remaining_red_balls = R - (A * mid)
remaining_yellow_balls = Y - (B * mid)
second_way = min(remaining_red_balls // B,
remaining_yellow_balls // A)
return first_way + second_way
def solve(R, Y, A, B):
lo, hi = 0, min(R // A, Y // B)
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__":
R, Y, A, B = 10, 12, 2, 5
print(solve(R, Y, A, B))
|
C#
using System;
public class Program
{
static int GetBoxes(int R, int Y, int A, int B, int mid)
{
int firstWay = mid;
int remainingRedBalls = R - (A * mid);
int remainingYellowBalls = Y - (B * mid);
int secondWay = Math.Min(remainingRedBalls / B, remainingYellowBalls / A);
return firstWay + secondWay;
}
static int Solve(int R, int Y, int A, int B)
{
int lo = 0, hi = Math.Min(R / A, Y / B);
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)
{
int R = 10, Y = 12, A = 2, B = 5;
Console.WriteLine(Solve(R, Y, A, B));
}
}
|
Javascript
function getBoxes(R, Y, A, B, mid) {
let firstWay = mid;
let remainingRedBalls = R - (A * mid);
let remainingYellowBalls = Y - (B * mid);
let secondWay = Math.min(Math.floor(remainingRedBalls / B), Math.floor(remainingYellowBalls / A));
return firstWay + secondWay;
}
function solve(R, Y, A, B) {
let lo = 0, hi = Math.min(Math.floor(R / A), Math.floor(Y / B));
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;
}
let R = 10, Y = 12, A = 2, B = 5;
console.log(solve(R, Y, A, B));
|
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)
|
