Tuesday, 26 Oct 2021

# 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: YESExplanation: fill first container with ball 1, second with 2 balls with number 3 and third container with ball having number 2Input: C = , B = [1, 2, 3]Output: NOExplanation: there’s no possible combination to fill the containersApproach: 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++#include using namespace std;  bool getans(int i, vector v, vector q){        if (i == q.size())        return true;          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;}  void Check(vector c, vector b){          map m;    for (int i = 0; i < b.size(); i++) {        m[b[i]]++;    }    vector v;    for (auto i : m) {        v.push_back(i.second);    }          bool check = getans(0, v, c);    if (check)        cout