Given three numbers W, B, and O representing the quantities of white, black, and other colors shirts respectively, the task is to find the maximum number of boxes required such that each box contains three shirts consisting of at least one white and black shirt using the given quantity of shirts.
Examples:
Input: W = 3, B = 3, O = 1
Output: 2
Explanation:
Below are the distribution of shirts in the boxes:
Box 1: 1 white shirt, 1 black shirt and 1 shirt of other color.
Box 2: 2 white shirts and 1 black shirt.
Box 3: 1 black shirt
Since, only 2 boxes satisfy the given condition which is the maximum possible number of boxes with the given quantity of shirts. Therefore, print 2.Input: W = 4, B = 6, O = 0
Output: 3
Approach: The given problem can be solved by using the Binary Search. The idea is to search for the maximum number of boxes in the search space formed by the lower and upper bound. It can be observed that the lower bound and the upper bound of the count of the box is 0 and minimum of W and B respectively. Follow the steps below to solve the problem:
- Initialize a variable, say ans as 0 to store the required result.
- Initialize two variables, say low as 0 and high as the minimum of (W, B).
- Loop until the value of low is less than high and perform the following steps:
- Find the middle value of low and high in a variable, say mid.
- Check if the maximum number of boxes can be equal to mid, then update the value of ans to mid and update the search space in the right half by updating the value of low.
- Otherwise, update the search space to the left half by updating the value of high.
- Print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum number// of boxes such that each box contains// three shirts comprising of at least// one white and black shirtvoid numberofBoxes(int W, int B, int O){ // Stores the low and high pointers // for binary search int low = 0, high = min(W, B); // Store the required answer int ans = 0; // Loop while low <= high while (low <= high) { // Store the mid value int mid = low + (high - low) / 2; // Check if the mid number of // boxes can be used if (((W >= mid) and (B >= mid)) and ((W - mid) + (B - mid) + O) >= mid) { // Update answer and recur // for the right half ans = mid; low = mid + 1; } // Else, recur for the left half else high = mid - 1; } // Print the result cout << ans;}// Driver Codeint main(){ int W = 3, B = 3, O = 1; numberofBoxes(W, B, O); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the maximum number// of boxes such that each box contains// three shirts comprising of at least// one white and black shirtstatic void numberofBoxes(int W, int B, int O){ // Stores the low and high pointers // for binary search int low = 0, high = Math.min(W, B); // Store the required answer int ans = 0; // Loop while low <= high while (low <= high) { // Store the mid value int mid = low + (high - low) / 2; // Check if the mid number of // boxes can be used if (((W >= mid) && (B >= mid)) && ((W - mid) + (B - mid) + O) >= mid) { // Update answer and recur // for the right half ans = mid; low = mid + 1; } // Else, recur for the left half else high = mid - 1; } // Print the result System.out.println(ans);}// Driver Codepublic static void main(String args[]){ int W = 3, B = 3, O = 1; numberofBoxes(W, B, O);}}// This code is contributed by avijitmondal1998 |
Python3
# Python3 program for the above approach# Function to find the maximum number# of boxes such that each box contains# three shirts comprising of at least# one white and black shirtdef numberofBoxes(W, B, O): # Stores the low and high pointers # for binary search low = 0 high = min(W, B) # Store the required answer ans = 0 # Loop while low <= high while (low <= high): # Store the mid value mid = low + (high - low) // 2 # Check if the mid number of # boxes can be used if (((W >= mid) and (B >= mid)) and ((W - mid) + (B - mid) + O) >= mid): # Update answer and recur # for the right half ans = mid low = mid + 1 # Else, recur for the left half else: high = mid - 1 # Print result print (ans)# Driver Codeif __name__ == '__main__': W = 3 B = 3 O = 1 numberofBoxes(W, B, O)# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;class GFG { // Function to find the maximum number // of boxes such that each box contains // three shirts comprising of at least // one white and black shirt static void numberofBoxes(int W, int B, int O) { // Stores the low and high pointers // for binary search int low = 0, high = Math.Min(W, B); // Store the required answer int ans = 0; // Loop while low <= high while (low <= high) { // Store the mid value int mid = low + (high - low) / 2; // Check if the mid number of // boxes can be used if (((W >= mid) &&(B >= mid)) &&((W - mid) + (B - mid) + O) >= mid) { // Update answer and recur // for the right half ans = mid; low = mid + 1; } // Else, recur for the left half else high = mid - 1; } // Print the result Console.Write(ans); } // Driver Code public static void Main() { int W = 3, B = 3, O = 1; numberofBoxes(W, B, O); }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript program for the above approach// Function to find the maximum number// of boxes such that each box contains// three shirts comprising of at least// one white and black shirtfunction numberofBoxes(W, B, O) { // Stores the low and high pointers // for binary search let low = 0, high = Math.min(W, B); // Store the required answer let ans = 0; // Loop while low <= high while (low <= high) { // Store the mid value let mid = low + Math.floor((high - low) / 2); // Check if the mid number of // boxes can be used if (((W >= mid) && (B >= mid)) && ((W - mid) + (B - mid) + O) >= mid) { // Update answer and recur // for the right half ans = mid; low = mid + 1; } // Else, recur for the left half else high = mid - 1; } // Print the result document.write(ans);}// Driver Codelet W = 3, B = 3, O = 1;numberofBoxes(W, B, O);// This code is contributed by gfgking</script> |
Output:
2
Time Complexity: O(log(min(W, B)))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
