Check if it’s possible to completely fill every container with the same ball

Algorithm

• In a map named 'ballFrequency', record the frequency of the same sort of ball.
• Create a vector named a ‘helper’ storing the frequency of every type of ball.
• To see if the containers can be filled, use the ‘checkFit’ function.
• Fill the container with balls that have a frequency that is more than the container's capacity. If it's possible, return true; else, go back and look for more balls.
• Return false if no combination exists.

Code:

#include <bits/stdc++.h>
using namespace std;

/*
     Check if it’s possible to completely fill every container with the map of 
     frequency using backtracking
*/
bool checkFit(int i, vector<int> helper, vector<int> container)
{

    // Base Case if reached to last index means all the containers are used
    if (i == container.size())
        return true;

    // Backtracking on all the frequencies
    for (int j = 0; j < helper.size(); j++) {
        if (helper[j] >= container[i]) {
            helper[j] -= container[i];
            if (checkFit(i + 1, helper, container)) {
                return true;
            }
            helper[j] += container[i];
        }
    }
    return false;
}

// Check if it’s possible to completely fill every container with the same ball
void ifPossible(vector<int> container, vector<int> ball)
{

    // For every type of ball store frequency
    map<int, int> ballFrequency;
    for (int i = 0; i < ball.size(); i++) ballFrequency[ball[i]]++;
    
    // Vector to store all the frequency
    vector<int> helper;
    for (auto i : ballFrequency) helper.push_back(i.second);
    

    // Function Call for backtracking
    if (checkFit(0, helper, container))
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

int main()
{

    // Given Input
    vector<int> container = { 1, 2,2 };
    vector<int> ball = { 1};

    // Check if it’s possible to completely fill every container with the same ball
    ifPossible(container, ball);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Time Complexity 

O(X ^ Y)

The time complexity to Check if it's possible to completely fill every container with the same ball is O(X ^ Y). Where ‘X’ is the size of the container array and ‘Y’ is the size of the ball array. Since, for every frequency of ball, we are exploring all the cases of container array, which will cost quadratic time complexity. In the worst case, every ball can have one frequency, so we will be iterating on all the elements of the ball array.

Space Complexity 

O(Y)

The space complexity to Check if it's possible to completely fill every container with the same ball is O(Y). Here ‘Y’ is the size of the ball array since we are creating an extra map and extra vector to store the frequencies of every type of ball. In the worst case, if all the balls have only a single frequency, then, in that case, we have to make the entire array of the ball.

FAQs

1. What is Backtracking?
   Backtracking is an algorithmic strategy that considers searching in every possible combination for solving the problem.
    
2. How is recursion different from Backtracking?
   In recursion, the function calls itself until it reaches a base case. We use recursion in backtracking to investigate all of the possibilities until we find the optimal solution to the problem.
    
3. Why do we use backtracking in this question?
   In such types of problems where we have to explore all the possibilities like which container is best suited for which type of ball the intitution should be toward recursion or Backtracking because backtracking will allow exploring all the possible solutions. 

Key Takeaways

In this blog, we discussed the solution to Check if it's possible to completely fill every container with the same ball along with the solution. We also explored the time and space complexity of the solution.

Recommended Readings:

• 8 Queens Problem Using Backtracking
   

If you want to learn more about Recursion and Backtracking and want to practice some quality questions which require you to excel your preparation s a notch higher, then you can visit our Guided Path for arrays on Coding Ninjas Studio.To be more confident in data structures and algorithms, try out our DS and Algo Course. Until then, All the best for your future endeavors, and Keep Coding.