Check if it’s possible to completely fill every container with same ball
Given two arrays, arr[ ] C of containers and arr[ ] B of balls, the task is to find if it’s possible to completely fill every container with the given balls, if each container can only store balls of the same type. In array C, C[i] stores the maximum number of balls that the i-th container can store. In array B, B[i] stores the type of the i-th ball.
Examples:
Input: C = [1, 2, 3], B = [1, 2, 2, 2, 3, 3, 4, 4, 4]
Output: YES
Explanation: fill first container with ball 1, second with 2 balls with number 3 and third container with ball having number 2Input: C = [2], B = [1, 2, 3]
Output: NO
Explanation: there’s no possible combination to fill the containers
Approach: The idea is to use Backtracking to check if it’s possible to fill every container or not. It can be observed that there is only a need for the frequency of each type of ball, so we store the frequency of each type of balls in a map. Lets look at the steps involved in implementation of our approach:
- Store the frequency of the same type of balls in a map.
- Call the function getans to check if its possible to fill the containers.
- Try to fill the container with balls whose frequency is more that equal to the container’s capacity. If its possible return true else backtrack and check for other balls.
- If no combination exists return false.
Below is the implementation of the above approach.
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // A boolean function that returns true if it's possible to // completely fill the container else return false bool getans( int i, vector< int > v, vector< int > q) { // Base Case if (i == q.size()) return true ; // Backtracking for ( int j = 0; j < v.size(); j++) { if (v[j] >= q[i]) { v[j] -= q[i]; if (getans(i + 1, v, q)) { return true ; } v[j] += q[i]; } } return false ; } // Function to check the conditions void Check(vector< int > c, vector< int > b) { // Storing frequencies map< int , int > m; for ( int i = 0; i < b.size(); i++) { m[b[i]]++; } vector< int > v; for ( auto i : m) { v.push_back(i.second); } // Function Call for backtracking bool check = getans(0, v, c); if (check) cout << "YES" << endl; else cout << "NO" << endl; } // Driver Code int main() { // Given Input vector< int > c = { 1, 3, 3 }; vector< int > b = { 2, 2, 2, 2, 4, 4, 4 }; // Function Call Check(c, b); return 0; } |
Java
// Java program for above approach import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; class GFG { // A boolean function that returns true if it's possible // to completely fill the container else return false static boolean getans( int i, List<Integer> v, int [] q) { // Base Case if (i == q.length) { return true ; } // Backtracking for ( int j = 0 ; j < v.size(); j++) { if (v.get(j) >= q[i]) { v.set(j, v.get(j) - q[i]); if (getans(i + 1 , v, q)) { return true ; } v.set(j, v.get(j) + q[i]); } } return false ; } // Function to check the conditions static void check( int [] c, int [] b) { // Storing frequencies Map<Integer, Integer> m = new HashMap<>(); for ( int i = 0 ; i < b.length; i++) { m.put(b[i], 0 ); } for ( int i = 0 ; i < b.length; i++) { m.put(b[i], m.get(b[i]) + 1 ); } List<Integer> v = new ArrayList<>(); for (Map.Entry<Integer, Integer> entry : m.entrySet()) { v.add(entry.getValue()); } // Function Call for backtracking boolean check = getans( 0 , v, c); if (check) { System.out.println( "YES" ); } else { System.out.println( "NO" ); } } // Driver Code public static void main(String[] args) { // Given Input int [] c = { 1 , 3 , 3 }; int [] b = { 2 , 2 , 2 , 2 , 4 , 4 , 4 }; // Function Call check(c, b); } } |
Python3
# Python 3 program for above approach # A boolean function that returns true if it's possible to # completely fill the container else return false def getans(i, v, q): # Base Case if (i = = len (q)): return True # Backtracking for j in range ( len (v)): if (v[j] > = q[i]): v[j] - = q[i] if (getans(i + 1 , v, q)): return True v[j] + = q[i] return False # Function to check the conditions def Check(c, b): # Storing frequencies m = {} for i in range ( len (b)): if b[i] in m: m[b[i]] + = 1 else : m[b[i]] = 1 v = [] for key,value in m.items(): v.append(value) # Function Call for backtracking check = getans( 0 , v, c) if (check): print ( "YES" ) else : print ( "NO" ) # Driver Code if __name__ = = '__main__' : # Given Input c = [ 1 , 3 , 3 ] b = [ 2 , 2 , 2 , 2 , 4 , 4 , 4 ] # Function Call Check(c, b) # This code is contributed by ipg2016107. |
C#
// C# program for above approach using System; using System.Collections.Generic; class GFG { // A boolean function that returns true if it's possible // to completely fill the container else return false static bool getans( int i, List< int > v, int [] q) { // Base Case if (i == q.Length) return true ; // Backtracking for ( int j = 0; j < v.Count; j++) { if (v[j] >= q[i]) { v[j] -= q[i]; if (getans(i + 1, v, q)) { return true ; } v[j] += q[i]; } } return false ; } // Function to check the conditions static void Check( int [] c, int [] b) { // Storing frequencies Dictionary< int , int > m = new Dictionary< int , int >(); for ( int i = 0; i < b.Length; i++) m[b[i]] = 0; for ( int i = 0; i < b.Length; i++) { m[b[i]]++; } List< int > v = new List< int >(); foreach (KeyValuePair< int , int > i in m) { v.Add(i.Value); } // Function Call for backtracking bool check = getans(0, v, c); if (check) Console.WriteLine( "YES" ); else Console.WriteLine( "NO" ); } // Driver Code public static void Main() { // Given Input int [] c = { 1, 3, 3 }; int [] b = { 2, 2, 2, 2, 4, 4, 4 }; // Function Call Check(c, b); } } // This code is contributed by ukasp. |
Javascript
<script> // Javascript program for above approach // A boolean function that returns true if it's possible to // completely fill the container else return false function getans(i, v, q) { // Base Case if (i == q.length) return true ; // Backtracking for (let j = 0; j < v.length; j++) { if (v[j] >= q[i]) { v[j] -= q[i]; if (getans(i + 1, v, q)) { return true ; } v[j] += q[i]; } } return false ; } // Function to check the conditions function Check(c, b) { // Storing frequencies let m = new Map(); for (let i = 0; i < b.length; i++) { if (m.has(b[i])) { m.set(b[i], m.get(b[i]) + 1); } else { m.set(b[i], 1); } } let v = []; for (i of m) { v.push(i[1]); } // Function Call for backtracking let check = getans(0, v, c); if (check) document.write( "YES" ); else document.write( "NO" ); } // Driver Code // Given Input let c = [1, 3, 3]; let b = [2, 2, 2, 2, 4, 4, 4]; // Function Call Check(c, b); // This code is contributed by _saurabh_jaiswal. </script> |
YES
Time Complexity: O(m^n), where n is the size of arr[ ] C and m is the size of arr[ ] B.
Auxiliary Space: O(m)
Contact Us