Check if all objects of type A and B can be placed on N shelves
Given two integers A and B, representing the count of objects of two different types, and another integer N which represents the number of shelves, the task is to place all objects in the given N shelves abiding by the following rules:
- Any shelf cannot contain both Type-A and Type-B objects at the same time.
- No shelf can contain more than K objects of Type-A or L objects of type B.
If it is possible to place all the items in N shelves, print “YES”. Otherwise, print “NO”.
Examples:
Input: A = 3, B = 3, N = 3, K = 4, M = 2
Output: YES
Explanation:
3 Type-A items can be placed on 1 shelf, as maximum limit is 4.
3 Type-B items can be placed on 2 shelves, as maximum limit is 2.
Since the required number of shelves does not exceed N, so allocation is possible.
Input: A = 6, B = 7, N = 3, K = 4, L = 5
Output: NO
Explanation:
6 Type-A items require 2 shelves, as maximum limit is 4.
7 Type-B items require 2 shelves, as maximum limit is 5.
Since the required number of shelves exceeds N, so allocation is not possible.
Approach:
To solve the problem, we need to count the minimum number of shelves required to place all objects and check if it exceeds N or not. Follow the steps below:
- Count the minimum number of items required to place Type-A items, say needa. Since, K Type-A items can be placed at most in a single shelf, following two conditions arise:
- If A is divisible by K, all Type-A items can be placed in A / K shelves.
- Otherwise, A % K items needs to be placed in 1 shelf and the rest in A / K shelves.Hence A/ K + 1 shelves are required for this case.
- Similarly, calculate the minimum number of shelves required to place Type-B items, say needb.
- If needa + needb exceeds N, allocation is not possible. Otherwise, it is possible.
Below is the implementation of the above approach.
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // Function to return if allocation // is possible or not bool isPossible( int A, int B, int N, int K, int L) { // Stores the shelves needed // for items of type-A and type-B int needa, needb; // Find number of shelves // needed for items of type-A if (A % K == 0) // Fill A / K shelves fully // by the items of type-A needa = A / K; // Otherwise else // Fill A / L shelves fully // and add remaining to an // extra shelf needa = A / K + 1; // Find number of shelves // needed for items of type-B if (B % L == 0) // Fill B / L shelves fully // by the items of type-B needb = B / L; else // Fill B / L shelves fully // and add remaining to an // an extra shelf needb = B / L + 1; // Total shelves needed int total = needa + needb; // If required shelves exceed N if (total > N) return false ; else return true ; } // Driver Program int main() { int A = 3, B = 3, N = 3; int K = 4, M = 2; if (isPossible(A, B, N, K, M)) cout << "YES" << endl; else cout << "NO" << endl; return 0; } |
Java
// Java implementation of the above approach class GFG{ // Function to return if allocation // is possible or not static boolean isPossible( int A, int B, int N, int K, int L) { // Stores the shelves needed // for items of type-A and type-B int needa, needb; // Find number of shelves // needed for items of type-A if (A % K == 0 ) // Fill A / K shelves fully // by the items of type-A needa = A / K; // Otherwise else // Fill A / L shelves fully // and add remaining to an // extra shelf needa = A / K + 1 ; // Find number of shelves // needed for items of type-B if (B % L == 0 ) // Fill B / L shelves fully // by the items of type-B needb = B / L; else // Fill B / L shelves fully // and add remaining to an // an extra shelf needb = B / L + 1 ; // Total shelves needed int total = needa + needb; // If required shelves exceed N if (total > N) return false ; else return true ; } // Driver code public static void main(String[] args) { int A = 3 , B = 3 , N = 3 ; int K = 4 , M = 2 ; if (isPossible(A, B, N, K, M)) System.out.print( "YES" + "\n" ); else System.out.print( "NO" + "\n" ); } } // This code is contributed by amal kumar choubey |
Python3
# Python3 implementation of the # above approach # Function to return if allocation # is possible or not def isPossible(A, B, N, K, L): # Stores the shelves needed # for items of type-A and type-B needa = 0 needb = 0 # Find number of shelves # needed for items of type-A if (A % K = = 0 ): # Fill A / K shelves fully # by the items of type-A needa = A / / K; # Otherwise else : # Fill A / L shelves fully # and add remaining to an # extra shelf needa = A / / K + 1 # Find number of shelves # needed for items of type-B if (B % L = = 0 ): # Fill B / L shelves fully # by the items of type-B needb = B / / L else : # Fill B / L shelves fully # and add remaining to an # an extra shelf needb = B / / L + 1 # Total shelves needed total = needa + needb # If required shelves exceed N if (total > N): return False else : return True # Driver Code if __name__ = = '__main__' : A, B, N = 3 , 3 , 3 K, M = 4 , 2 if (isPossible(A, B, N, K, M)): print ( 'YES' ) else : print ( 'NO' ) # This code is contributed by rutvik_56 |
C#
// C# implementation of the above approach using System; class GFG{ // Function to return if allocation // is possible or not static bool isPossible( int A, int B, int N, int K, int L) { // Stores the shelves needed // for items of type-A and type-B int needa, needb; // Find number of shelves // needed for items of type-A if (A % K == 0) // Fill A / K shelves fully // by the items of type-A needa = A / K; // Otherwise else // Fill A / L shelves fully // and add remaining to an // extra shelf needa = A / K + 1; // Find number of shelves // needed for items of type-B if (B % L == 0) // Fill B / L shelves fully // by the items of type-B needb = B / L; else // Fill B / L shelves fully // and add remaining to an // an extra shelf needb = B / L + 1; // Total shelves needed int total = needa + needb; // If required shelves exceed N if (total > N) return false ; else return true ; } // Driver code public static void Main(String[] args) { int A = 3, B = 3, N = 3; int K = 4, M = 2; if (isPossible(A, B, N, K, M)) Console.Write( "YES" + "\n" ); else Console.Write( "NO" + "\n" ); } } // This code is contributed by Rohit_ranjan |
Javascript
<script> // JavaScript program to implement // the above approach // Function to return if allocation // is possible or not function isPossible(A, B, N, K, L) { // Stores the shelves needed // for items of type-A and type-B let needa, needb; // Find number of shelves // needed for items of type-A if (A % K == 0) // Fill A / K shelves fully // by the items of type-A needa = Math.floor(A / K); // Otherwise else // Fill A / L shelves fully // and add remaining to an // extra shelf needa = Math.floor(A / K) + 1; // Find number of shelves // needed for items of type-B if (B % L == 0) // Fill B / L shelves fully // by the items of type-B needb = Math.floor(B / L); else // Fill B / L shelves fully // and add remaining to an // an extra shelf needb = Math.floor(B / L) + 1; // Total shelves needed let total = needa + needb; // If required shelves exceed N if (total > N) return false ; else return true ; } // Driver code let A = 3, B = 3, N = 3; let K = 4, M = 2; if (isPossible(A, B, N, K, M)) document.write( "YES" + "<br/>" ); else document.write( "NO" + "<br/>" ); // This code is contributed by sanjoy_62. </script> |
YES
Time complexity: O(1)
Auxiliary Space: O(1)