Organizing Containers of Balls

Problem Statement of Organizing Containers of Balls Challenge

We are give few containers containing balls of different colors. We can exchange same number of balls between any two containers. Which means suppose we put two balls from container Ci to Cj then two balls will be put in Ci from Cj. With this exchange operation, can we reorganize the balls in containers in such a ways, so that all the containers have all balls in it of same color? If possible the say POSSIBLE otherwise IMPOSSIBLE. The original statement of Organizing Containers of Balls challenge is available on Hackerrank.

Why is it not a difficult challenge?

At first it seems that the problem is very difficult and the logic to solve this problem will involve deriving all possible exchanges of balls we can make among containers. But the challenge should be approached with this strategy only if the steps of exchange are also asked. But the problem is not asking how will you do it. It is just asking can you do it.

That’s the catch in most of the Hackathon problems. If the challenge requires answer in YES or NO for any task or the number of possibilities for any event is asked, then be sure that we don’t have to actually do the task. We just have to determine whether the task can be done or not or we have to find the way to count the possibilities without actually performing the task. In this challenge also, we are going to do the same.

Big Idea for Organizing Containers of Balls

As per the challenge description, we can only exchange same number of balls between any two containers but we can transfer one or more balls from one container to another without taking back the same number of balls from that container.  This point concludes that the number of balls in each container will never change. In other words we can say the capacity of containers will not change.

This means we will be able to put all balls of same color in each container only if –

1. The number of colors of balls must be exactly equal to number of containers.
2. There should be a one to one mapping between colors and containers such that number of ball of a color must be equal to capacity of the mapped container.

Example

Suppose we have 3 containers having capacity of 3, 4 and 8 respectively. Then the answer will be POSSIBLE only if the there are balls of only three colors (not less, not more) and the number of balls all three colors must 3, 4 and 8, not necessarily in same order.

How to answer queries?

The input in the problem is given as matrix, where row denotes container and column denotes color. For example-

Organizing Containers of Balls

The input is interpreted as container 1 contains 1 ball of color 1, 3 balls of color 2 and 1 ball of color 3. Similarly for rest of the rows.

So, if we take sum of a row then we will get capacity of that container. Suppose the capacity of each container is represented as an array CAP. For above problem CAP is generated by taking sum of all rows separately.

Organizing Containers of Balls

Similarly, sum of each column represents number of balls of that particular color. Suppose the number of balls of each color are put in an array called COL. For above problem COL is generated by taking sum of each column separately.

Organizing Containers of Balls

Now, the arrays CAP and COL should have same elements (not necessarily in same order). In this case CAP contains 5, 5, 9 and COL contains 6, 7, 6. These do not match and the answer will be IMPOSSIBLE.
Let’s take another example, Input is given as-

Organizing Containers of Balls

CAP->

Organizing Containers of Balls

COL->

Organizing Containers of Balls

Both, CAP and COL have two 3’s and one 2. So in this case the answer is POSSIBLE.

How to check whether two arrays have same elements?

Suppose we have two arrays A and B of same size and we have to determine whether both arrays have same elements of not.

O(nlogn) Approach

The basic approach is to sort both arrays and compare index by index. If for any index I, A[i] is not equal to B[i], then answer is no, otherwise yes. This approach will take atleast o(nlogn) time to sort and O(n) time to compare elements of both arrays.

O(n) Approach

Take a frequency array FREQ of size K (K is the larges element of both arrays). Initialize all the positions of FREQ with zero. Then count frequency of each element of array A as follows-

for(i = 1 to n)
            FREQ[A[i]] ++;

Now, the frequency (stored in FREQ) of a particular element will be reduced if it is present in B. It is done in following way-

for(i = 1 to n)
            FREQ[B[i]]--;

After both for loops if all the elements of FREQ are zero then A and B contain exactly same elements.

Recommended Posts-
Append and Delete
Circular Array Rotation
Insertion Sort Advanced Analysis
Can we ditch python for competitive coding?
5 C functions for competitive programming?
Prefix Sum : Query Time O(1) : Pre-processing Time O(n)

Spread the love

Leave a Comment

Your email address will not be published. Required fields are marked *