Distribute R,B beans such that each packet has at least 1 R and 1 B bean with absolute difference at most D
Given two positive integers R and B representing R red and B blue beans and an integer D, the task is to check whether it is possible to distribute the beans among several (maybe, one) packets according to the following rules:
- Each packet has at least one red bean.
- Each packet has at least one blue bean.
- The number of red and blue beans in each packet should differ in no more than D (or |R-B| <= D)
Print Yes if it is possible. Otherwise, print No.
Examples
Input: R = 1, B = 1, D = 0
Output: Yes
Explanation: Form one packet with 1 red and 1 blue bean. The absolute difference |1?1| = 0 ? D.Input: R = 6, B = 1, D = 4
Output: No
Approach: This problem can be solved easily by observing that the maximum of (R and B) is D + 1 times the minimum of R and B. Follow the steps given below to solve the problem:
- Find the maximum of R and B. and the minimum of R and B.
- To satisfy the given 3 constraints, the value of the max(R, B) should be at most (D + 1) times min(R, B), because (D + 1) beans can be kept in each packet, 1 bean of one type, and D beans of the other type.
- After completing the above steps, print “Yes” if the value of the max(R, B) is less than or equal to (D + 1)*min(R, B). Otherwise, print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if it is possible // to distribute R red and B blue beans // in packets such that the difference // between the beans in each packet is // atmost D void checkDistribution( int R, int B, int D) { // Check for the condition to // distributing beans if (max(R, B) <= min(R, B) * (D + 1)) { // Print the answer cout << "Yes" ; } // Distribution is not possible else { cout << "No" ; } } // Driver Code int main() { int R = 1, B = 1, D = 0; checkDistribution(R, B, D); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to check if it is possible // to distribute R red and B blue beans // in packets such that the difference // between the beans in each packet is // atmost D static void checkDistribution( int R, int B, int D) { // Check for the condition to // distributing beans if (Math.max(R, B) <= Math.min(R, B) * (D + 1 )) { // Print the answer System.out.println( "Yes" ); } // Distribution is not possible else { System.out.println( "No" ); } } // Driver Code public static void main(String[] args) { int R = 1 , B = 1 , D = 0 ; checkDistribution(R, B, D); } } // This code is contributed by Potta Lokesh |
Python3
# Python3 program for the above approach # Function to check if it is possible # to distribute R red and B blue beans # in packets such that the difference # between the beans in each packet is # atmost D def checkDistribution(R, B, D): # Check for the condition to # distributing beans if ( max (R, B) < = min (R, B) * (D + 1 )): # Print the answer print ( "Yes" ) # Distribution is not possible else : print ( "No" ) # Driver Code R = 1 B = 1 D = 0 checkDistribution(R, B, D) # This code is contributed by code_hunt |
C#
// C# program for the above approach using System; class GFG{ // Function to check if it is possible // to distribute R red and B blue beans // in packets such that the difference // between the beans in each packet is // atmost D static void checkDistribution( int R, int B, int D) { // Check for the condition to // distributing beans if (Math.Max(R, B) <= Math.Min(R, B) * (D + 1)) { // Print the answer Console.WriteLine( "Yes" ); } // Distribution is not possible else { Console.WriteLine( "No" ); } } // Driver code static public void Main() { int R = 1, B = 1, D = 0; checkDistribution(R, B, D); } } // This code is contributed by target_2. |
Javascript
<script> // JavaScript program for the above approach // Function to check if it is possible // to distribute R red and B blue beans // in packets such that the difference // between the beans in each packet is // atmost D function checkDistribution(R, B, D) { // Check for the condition to // distributing beans if (Math.max(R, B) <= Math.min(R, B) * (D + 1)) { // Print the answer document.write( "Yes" ); } // Distribution is not possible else { document.write( "No" ); } } // Driver Code let R = 1, B = 1, D = 0; checkDistribution(R, B, D); // This code is contributed by sanjoy_62. </script> |
Output
Yes
Time Complexity: O(1)
Auxiliary Space: O(1)